ChunNote
0%

leetCode-685:Redundant Connection II

发表于 分类于

问题描述

给定一个二维数组表示边 [u, v] 的集合，每条边表示 u 到 v 有一条连线，且 u 是 v 的父节点，这些边连接后构成一个有向连通图，其中存在一条多余的边，要求将这条边找出并剔除，使得剩下的图不存在环结构，同时仍然保持是一个有向的连通图。如果存在多条边，则返回最后出现的那条边。题目链接：**点我**

样例输入输出

输入：[[1,2], [2,3], [3,4], [4,1], [1,5]]

输出：[4,1]

输入：[[2,1], [3,1], [4,2], [1,4]]

输出：[2,1]

问题解法

此题跟 LeetCode-684 类似，不同的是 LeetCode-684 是无向图，而这题是有向图。针对此题，仍然可以使用并查集进行求解，不同的是不能单纯的判断是否存在环，否则对于输入[[2,1], [3,1], [4,2], [1,4]] 得到的结果是 [1,4] 而不是 [2,1]。针对此问题，观察得知，可能存在某个节点的入度为 2，即某个节点拥有两个父节点，这两条边必然需要去除一条边。所以，可以在排除这两条边的情况下运用并查集构建图，然后依次加入这两条边，如果加入某条边时构成了环，说明这条边是多余的，需要去除。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution
{
    public int[] findRedundantDirectedConnection(int[][] edges)
    {
        int[] parents = new int[edges.length + 1];
        boolean[] isUsed = new boolean[edges.length + 1];
        int duplicateNode = -1;
        for (int[] edge : edges)
        {
            if (isUsed[edge[1]])
            {
                duplicateNode = edge[1];
                break;
            }

            isUsed[edge[1]] = true;
        }

        List<int[]> remainEdgeList = new LinkedList<>();
        for (int[] edge : edges)
        {
            if (edge[1] != duplicateNode)
            {
                if (isFindEdge(parents, edge))
                {
                    return edge;
                }
            }
            else
            {
                remainEdgeList.add(edge);
            }
        }

        for (int[] edge : remainEdgeList)
        {
            if (isFindEdge(parents, edge))
            {
                return edge;
            }
        }

        return new int[0];
    }

    private boolean isFindEdge(int[] parents, int[] edge)
    {
        int uParent = findParent(parents, edge[0]);
        int vParent = findParent(parents, edge[1]);
        if (uParent == vParent)
        {
            return true;
        }

        parents[vParent] = uParent;
        return false;
    }

    private int findParent(int[] parents, int i)
    {
        if (parents[i] == 0)
        {
            return i;
        }

        int root = findParent(parents, parents[i]);
        parents[i] = root;
        return root;
    }
}