LeetCode/685. 冗余连接 II

685. 冗余连接 II

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例1 ：

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3

示例 2：

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
    ^    |
    |    v
    4 <- 3

注意:

• 输入的二维数组大小在 3 到 1000。
• 二维数组中的整数在1到N之间，其中N是输入数组的大小。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题是在684. 冗余连接的基础上将无向图换成有向图，我们要明确题目的定义，即有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。所以有两种情况我们需要考虑。第一种就是就是像上一题一样虽然没有构成环，但是增加了这条边后，不能构成有向树，即不能保证每个节点只有一个父节点，对应[[1,2],[1,3],[2,3]]这种情况。第二种情况就是构成了有向图中的环，对应[[2,1],[3,1],[4,2],[1,4]]。针对上述两种问题，我们分别来讨论，第一种情况，我们遍历edges数组，如果每条edge的两个节点对应的parent[i]为0，说明这两个节点都是新节点，如果当前节点的parent[i]不为0，则说明已经有一条路径存在，加上这条边就不满足有根树的条件，所以我们将原先路径和新的路径保存，最后直接返回该边即可。对于第二种情况，这里和上一题思路一样，直接用并查集的思想去做就可以了。

具体代码如下：

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int[] parents = new int[edges.length + 1];
        int[] roots = new int[edges.length + 1];
        int[] sizes = new int[edges.length + 1];
        Arrays.fill(sizes, 1);

        int[] ans1 = new int[2];
        int[] ans2 = new int[2];

        //第一部分用于查找每个结点的parents是谁
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            if (parents[v] > 0) {
                ans1 = new int[]{parents[v], v};
                ans2 = new int[]{edge[0], edge[1]};

                edge[0] = edge[1] = -1;
            }
            parents[v] = u;
        }

        //第二部分用于查找环
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            if (u < 0 || v < 0) continue;

            if (roots[u] == 0) roots[u] = u;
            if (roots[v] == 0) roots[v] = v;

            int pu = find(u, roots);
            int pv = find(v, roots);

            if (pu == pv) {
                if (ans1[0] == 0 && ans1[1] == 0)
                    return edge;
                else return ans1;
            }

            if (sizes[pv] > sizes[pu]) {
                int temp = pv;
                pv = pu;
                pu = temp;
            }

            roots[pv] = pu;
            sizes[pu] += sizes[pv];
        }
        return ans2;
    }

    int find(int target, int[] parents) {
        while (parents[target] != target) {
            parents[target] = parents[parents[target]];
            target = parents[target];
        }
        return target;
    }

}