Paths in Maze That Lead to Same Room

Statement#

A maze consists of $n$ rooms numbered from $1 - n$, and some rooms are connected by corridors. You are given a 2D integer array, corridors, where $corridors[i] = [room1, room2]$ indicates that there is a corridor connecting $room1$ and $room2$, allowing a person in the maze to go from $room1$ to $room2$ and vice versa.

The designer of the maze wants to know how confusing the maze is. The confusion score of the maze is the number of different cycles of length 3.

For example, $1 → 2 → 3 → 1$ is a cycle of length $3$, but $1 → 2 → 3 → 4$ and $1 → 2 → 3 → 2 → 1$ are not.

Two cycles are considered to be different if one or more of the rooms visited in the first cycle is not in the second cycle.

Return the confusion score of the maze.

Constraints:

• $2 \leq$ n $\leq 1000$
• $1 \leq$ corridors.length $\leq 5 \times 10^4$
• corridors[i].length $= 2$
• $1 \leq room1_i, room2_i \leq n$
• $room1_i \neq room2_i$
• There are no duplicate corridors.

Examples#

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself#

Implement your solution in the following coding playground.