684. 冗余连接

主要掌握并查集/dfs/拓扑排序.
dfs里要注意从后面开始查，特别是dfs函数如何设计以及

public int[] findRedundantConnection(int[][] edges) {
        ArrayList<Integer>[] lists = new ArrayList[edges.length + 1];
        for (int i = 0; i < edges.length+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int[] temp = edges[i];
            if (lists[temp[0]] == null) {
                lists[temp[0]] = new ArrayList<>();
            }
            lists[temp[0]].add(temp[1]);

            if (lists[temp[1]] == null) {
                lists[temp[1]] = new ArrayList<>();
            }
            lists[temp[1]].add(temp[0]);
        }
     
        for (int i = edges.length-1; i >= 0; i--) {
            int[] indegrees = new int[edges.length+1];
            int i1 = edges[i][0];
            int i2 = edges[i][1];
            if(!dfs(lists, indegrees, i2, i1, i1)) {
                return new int[]{edges[i][0], edges[i][1]};
            }
        }
        return null;
    }

    public boolean dfs(ArrayList<Integer>[] map, int[] indegrees, int cur, int pre, int y) {
        if(cur == y) {
            return false;
        }
        if(indegrees[cur] == 1) {
            return true;
        }
        if(indegrees[cur] == 2) {
            return true;
        }
        indegrees[cur] = 1;
        ArrayList<Integer> nexts = map[cur];
        for (int i = 0; i < nexts.size(); i++) {
            if(nexts.get(i) == pre) {
                continue;
            }
            if(!dfs(map, indegrees, nexts.get(i), cur, y)) {
                return false;
            }
        }
        indegrees[cur] = 2;
        return true;
    }

    //拓扑排序
    //拓扑注意度的变化
    public int[] findRedundantConnection1(int[][] edges) {
        ArrayList<Integer>[] lists = new ArrayList[edges.length + 1];
        for (int i = 0; i < edges.length+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int[] temp = edges[i];
            if (lists[temp[0]] == null) {
                lists[temp[0]] = new ArrayList<>();
            }
            lists[temp[0]].add(temp[1]);

            if (lists[temp[1]] == null) {
                lists[temp[1]] = new ArrayList<>();
            }
            lists[temp[1]].add(temp[0]);
        }
        int[] indegrees = new int[edges.length+1];
        for (int i = edges.length-1; i >= 0; i--) {
            indegrees[edges[i][0]]++;
            indegrees[edges[i][1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= edges.length; i++) {
            if(indegrees[i] == 1) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int index = queue.poll();
            ArrayList<Integer> list = lists[index];
            for (int i = 0; i < list.size(); i++) {
                int next = list.get(i);
                if(--indegrees[next] == 1) {
                    queue.add(next);
                }
            }
        }
        for (int i = edges.length; i > 0; i--) {
            if(indegrees[edges[i][0]]>1 && indegrees[edges[i][0]] > 1) {
                return edges[i];
            }
        }
        return  new int[0];
    }
    //并查集。里面加了秩
    public int[] findRedundantConnection2(int[][] edges) {
        int[] parent = new int[edges.length+1];
        int rank[] = new int[edges.length+1];
        for (int i = 1; i < edges.length+1; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            if(!unin(parent, rank, x, y)) {
                return edges[i];
            }
        }
        return null;

    }

    public int find(int[] parent, int x) {
        if(parent[x] == x) {
            return x;
        } else {
            return find(parent, parent[x]);
        }
    }

    public boolean unin(int[] parent, int[] rank, int x, int y) {
        int xParent = find(parent, x);
        int yPanrent = find(parent, y);
        if(xParent == yPanrent) return false;
        int xRank = rank[xParent];
        int yRank = rank[yPanrent];
        if(xRank < yRank) {
            parent[x] = yPanrent;
            parent[xParent] = yPanrent;
        } else if(xRank > yRank) {
            parent[y] = xParent;
            parent[yPanrent] = xParent;
        } else {
            parent[x] = yPanrent;
            parent[xParent] = yPanrent;
            rank[yPanrent]++;
        }
        return true;

    }