# 2077. Paths in Maze That Lead to Same Room
###### tags: `Leetcode` `Medium` `Graph`
Link: https://leetcode.com/problems/paths-in-maze-that-lead-to-same-room/description/
## 思路 $O(VE)$
### 方法一
从每个点开始 找到他们往下两步能到的点 如果和起点一样 那么答案就加一
### 方法二
对于每一个corridor的两个点
检查他们所能连到的点是否有重合的 如果有意味着confusing score要加1
为了避免重复 例如一个corridor是```(a,b) a<b``` ```graph[a]```里面会有```b``` ```graph[b]```没有```a```
## Code
### 方法一

class Solution:
    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
        graph = collections.defaultdict(set)
        ans = 0
        for a, b in corridors:
            graph[a].add(b)
            graph[b].add(a)
        
        def dfs(cur, start, depth):
            nonlocal ans
            if depth == 3:
                if start in graph[cur]:
                    ans += 1
                return
            
            for nextNode in graph[cur]:
                if nextNode<cur: continue
                dfs(nextNode, start, depth+1)


        for i in range(1, n+1):
            dfs(i, i, 1)
        
        return ans

### 方法二

class Solution:
    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
        graph = defaultdict(set)
        for a, b in corridors:
            if a<b: graph[a].add(b)
            else: graph[b].add(a)
        
        ans = 0
        for a, b in corridors:
            ans += len(graph[a].intersection(graph[b]))
        return ans

class Solution {
    public int numberOfPaths(int n, int[][] corridors) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for(int i=1; i<=n; i++){
            graph.put(i, new HashSet<>());
        }
        for(int[] e:corridors){
            if(e[0]<e[1]) graph.get(e[0]).add(e[1]);
            else graph.get(e[1]).add(e[0]);
        }
        int ans = 0;
        for(int[] e:corridors){
            Set<Integer> s1 = graph.get(e[0]);
            Set<Integer> s2 = graph.get(e[1]);
            for(int k:s1){
                if(s2.contains(k)) ans++;
            }
        }
        return ans;
    }
}