# 2204. Distance to a Cycle in Undirected Graph
###### tags: `Leetcode` `Hard` `Topological Sort` `BFS`
Link: https://leetcode.com/problems/distance-to-a-cycle-in-undirected-graph/
## 思路
参考[这里](https://leetcode.com/problems/distance-to-a-cycle-in-undirected-graph/discuss/1894719/Outside-In-and-Inside-Out)
先topological sort找到cycle
然后从cycle的每个点出发 层序遍历 找到每个node的distance
这里要注意的是：
之前做过的topological sort都是directed graph
这题是undirected graph
所以建graph的时候要把两个方向都加进去 同时degree=1就可以加到queue里面 因为degree=1说明当前点是leave
## Code

class Solution {
    public int[] distanceToCycle(int n, int[][] edges) {
        int[] ans = new int[n];
        List<List<Integer>> graph = new ArrayList<>();
        int[] degree = new int[n];
        
        for(int i=0; i<n; i++){
            graph.add(new ArrayList<>());
        }
        for(int[] edge:edges){
            int prev = edge[0];
            int next = edge[1];
            graph.get(prev).add(next);
            graph.get(next).add(prev);
            degree[prev]++;
            degree[next]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<n; i++){
            if(degree[i]==1) q.add(i);
        }
        
        while(!q.isEmpty()){
            int curr = q.poll();
            for(int next:graph.get(curr)){
                if(degree[next]==1) continue;
                degree[next]--;
                if(degree[next]==1) q.add(next);
            }
        }
        
        Queue<Integer> q2 = new LinkedList<>();
        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++){
            if(degree[i]!=1){
                ans[i]=0;
                visited[i]=true;
                q2.add(i);
            }
        }
        
        int step = 1;
        while(!q2.isEmpty()){
            int size = q2.size();
            for(int i=0; i<size; i++){
                int curr = q2.poll();
                for(int next:graph.get(curr)){
                    if(visited[next]) continue;
                    ans[next] = step;
                    q2.add(next);
                    visited[next] = true;
                }
            }
            step++;
        }
        
        return ans;
    }
}