2077. Paths in Maze That Lead to Same Room

A maze consists of n rooms numbered from 1 to n, and some rooms are connected by corridors. You are given a 2D integer array corridors where corridors[i] = [room1i, room2i] indicates that there is a corridor connecting room1i and room2i, allowing a person in the maze to go from room1i to room2i 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.

class Solution {
    vector<vector<int>> adj;
    vector<unordered_set<int>> radj;
    int dfs(int root, int u, int d, int par) {
        if(d == 2) return radj[u].count(root);
        int res = 0;
        for(auto& v : adj[u]) {
            if(v == par) continue;
            res += dfs(root, v, d + 1, u);
        }
        return res;
    }
public:
    int numberOfPaths(int n, vector<vector<int>>& corridors) {
        adj = vector<vector<int>>(n+1);
        radj = vector<unordered_set<int>>(n + 1);
        for(auto c : corridors) {
            int u = c[0], v = c[1];
            adj[min(u,v)].push_back(max(u,v));
            radj[max(u,v)].insert(min(u,v));
        }
        
        long long res = 0;
        
        for(int i = 1; i <= n; i++) res += dfs(i,i,0,-1);
        
        return res;
    }
};