685. 冗余连接 II

Problem: 685. 冗余连接 II

思路

和上一题不同的是，这题把无向图换成了有向图，树的要求也更严格了。

同过观察用例，可以发现加上一条边后有两种情况使得树不再成立：

1. 一个节点有两个入度。
2. 形成了有向环。

这两种情况是相互交叉的，可能会同时发生。但是删掉最后的导致成环的边不一定能够消除两个入度的边，所以我们优先找出有两个入度的边。

找到有两个入度的边后，我们从后往前进行判断，如果删去这条边能够构成树，那么我们就找到了答案。而要判断删去一个边能否构成树，我们也可以用到并查集：先用其他边构建一个节点的并查集，然后判断这条边的两个节点是否在同一个并查集中，如果是的话删掉这条边就是可行的。

如果没有两个入度的边，我们就寻找最后导致成环的边即可。参考上一题的思路，可以很自然地想到用并查集解决。

一开始想到了这个思路但是没有去实现，因为觉得这样代码太复杂不够简洁。看了题解发现代码确实多，说明图论的题目有时候代码量是会很大。

树的图性质

通过这两道题我们可以发现，树在图论里可以很自然地和并查集联系在一起。并查集本身就是树形结构，和树一样都只有一个根节点。以后遇到相关的题目可以优先考虑是否可以使用并查集。

图

图论的题目，从入度、出度、增减边、边的性质来考虑看起来是很有效的。

复杂度

• 时间复杂度: $O(nlogn)$
• 空间复杂度: $O(n)$

Code

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] in = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            in[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            if (in[edges[i][1]] != -1) {
                if (isTree(edges, i)) return edges[i];
                return edges[in[edges[i][1]]];
            }
            in[edges[i][1]] = i;
        }
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            if (find(parent, edges[i][1]) == find(parent, edges[i][0])) return edges[i];
            else {
                union(parent, edges[i][1], edges[i][0]);
            }
        }
        return new int[0];
    }

    public boolean isTree(int[][] edges, int index) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            if (i != index ) union(parent, edges[i][1], edges[i][0]);
        }
        return find(parent, edges[index][0]) == find(parent, edges[index][1]);
    }

    public void union(int[] parent, int a, int b) {
        parent[find(parent, a)] = find(parent, b);
    }

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