# \[685]\[困难]\[并查集] 冗余连接 II

## 题目描述

[685. 冗余连接 II](https://leetcode-cn.com/problems/redundant-connection-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 是二维数组的大小。

## 解题思路

[685. 冗余连接 II:【并查集的应用】详解](https://leetcode-cn.com/problems/redundant-connection-ii/solution/685-rong-yu-lian-jie-iibing-cha-ji-de-ying-yong-xi/) [python 简洁代码 并查集的运用](https://leetcode-cn.com/problems/redundant-connection-ii/solution/python-jian-ji-dai-ma-bing-cha-ji-de-yun-yong-by-y/)

根据题目的描述, 给出的有向图是由**有着**$$N$$**个节点的树**, 以及**一条附加的边**构成, 也就是说只是由一条边破坏了树的结构. 想想一棵树中添加一条边, 会有以下几种情况.

**所有节点的入度仍为1, 但形成了环**

在一棵树中, 除了根节点的入度为0, 其余节点的入度都是1. 因此这种情况对应的就是从叶子节点向根节点连了条线作为附加的边. 因此肯定会形成一个有向环. 这种情况下的环, 去掉环中的任意一条边, 整个图都会回复成一棵树.

因此在遍历边的过程中, 当前边指向的节点(有向图)如果还没有被连接过(保证连接后入度为1), 在更新**并查集**之前, 发现连接后可能成环, 即当前边两端节点在并查集中的父节点是同一个节点时, 将这条边记录, 在最后剔除.

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F10951dc250e3efcfa4cbc9334a818b008d3f8c49.png?generation=1601089832101025\&alt=media)

**有节点入度为2**

如果连接后入度为2, 说明要连接的这条边指向的节点, 之前已经产生了连接. 那么要删掉的边要么是该节点之前已经连接的边, 要么是当前这条边. 将这两条边都记录下来, 而且最新的这条边不并入到图中, 即不依据此边更新并查集(也说明已经连接的那条边已经并入了并查集). 继续更新其他边.

最终如果图中有环, 如下图的情况1, 即1, 2, 4三个点成环, 由于会引发入度为2的那条边没有被引入到图中, 而有环说明边`(1, 2)`是加入到图中的, 因此对于2节点, 是先遇到了`(1, 2)`再遇到了`(3, 2)`. 这种情况, 引发成环的那条边一定是之前已经被引入的`(1, 2)`这条边, 因此删除的也应当是这条边.

如果最终没有环, 即下图的情况2, 对于节点3, 其实删除哪一条边都可以, 但因为引发入度为2的边, 即没有加入图(并查集)的边是后来的, 根据题目要求应该删除这条边.

总结入度为2的情况, 当新来的一条边引发入度为2的情况, 先不将这条边加入到图(并查集)中, 而是按照边出现的先后顺序, 即已加入的在先, 新来的当前边在后的顺序, 存储在一个候选列表中, 继续遍历其他边. 最终当图中有环时, 一定是由靠前的边引起的, 删除候选列表中的第一条边; 否则删除任意一条都可以, 但按题目要求, 删除候选列表中的最后一条, 即第二条边.

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fab833087e1c6cd5236d2c27d3fa9eb6ab9d3ae67.png?generation=1601089831933429\&alt=media)

剩余的就是实现上面逻辑判断的技巧.

使用并查集维护一张图, 这样可以快速的判断两个点是否拥有共同的祖先, 如果有共同的祖先再连一条合适的有向边, 一定就会成环了. 利用并查集的特性快速判断图中是否有环.

入度的维护使用**字典**. 在遍历到一条边时, 如果需要将这条边更新到图中, 除了更新并查集, 还要以有向边指向的节点为`key`, 出发的节点为`value`, 更新字典, 代表某个节点的父节点, 因此如果新边所指向的节点, 如果在字典中有对应的`key`, 说明入度已经为1了, 这时就发生了入度为2的问题.

使用两个列表, 分别存储入度为2的冲突边, 和引发形成环的边. 而且对于形成环的边, 都是要更新到图中的. 因为无论是哪种成环的情况, 我们都已经记录了要删除的边, 在最后删除就好. 引入成环边并不影响后续边的逻辑判断.

```python
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))

    def find(self, i):
        if i == self.root[i]:
            return i
        self.root[i] = self.find(self.root[i])
        return self.root[i]

    def union(self, i, j):
        self.root[self.find(j)] = self.find(i)

    def connected(self, i, j):
        return self.find(i) == self.find(j)

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UnionFind(len(edges))
        parents = dict()
        candidates, circle = [], []
        for start, end in edges:
            if end in parents:
                candidates.append([parents[end], end])
                candidates.append([start, end])
            else:
                if uf.connected(start, end):
                    circle.append([start, end])
                uf.union(start, end)
                parents[end] = start

        if not candidates:
            return circle[-1]
        return candidates[0] if circle else candidates[-1]
```