Solution: Paths in Maze That Lead to Same Room

Understand how to analyze maze rooms as a graph to detect cycles of length three, also known as triangular cycles. Learn both naive and optimized approaches using depth-first search and adjacency lists to efficiently count such cycles. This lesson helps you implement scalable graph algorithms in C# to solve coding interview problems involving cycle detection.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using graph algo

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$ ...