# halfrost/LeetCode-Go

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
685. Redundant Connection II.go
685. Redundant Connection II_test.go

# 685. Redundant Connection II

## 题目:

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of `edges`. Each element of `edges` is a pair `[u, v]` that represents a directed edge connecting nodes `u` and `v`, where `u` is a parent of child `v`.

Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

Example 1:

``````Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given directed graph will be like this:
1
/ \
v   v
2-->3
``````

Example 2:

``````Input: [[1,2], [2,3], [3,4], [4,1], [1,5]]
Output: [4,1]
Explanation: The given directed graph will be like this:
5 <- 1 -> 2
^    |
|    v
4 <- 3
``````

Note:

• The size of the input 2D-array will be between 3 and 1000.
• Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

## 题目大意

• 二维数组大小的在 3 到 1000 范围内。
• 二维数组中的每个整数在 1 到 N 之间，其中 N 是二维数组的大小。

## 解题思路

• 这一题是第 684 题的加强版。第 684 题中的图是无向图，这一题中的图是有向图。
• 这一题的解法也是用并查集，不过需要灵活一点，不要用模板，因为在模板中，存在路径压缩和 `rank()` 优化，这些优化会改变有向边原始的方向。所以并查集只需要记录 `parent()` 就够用了。

• 经过分析，可以得到上面这 3 种情况，红色的边是我们实际应该删除的。先来看情况 2 和情况 3 。当不断 `union()` 时，加入一条边以后，会使一个节点的入度变成 2，那么记录下这两条边为 `candidate1``candidate2`。将后加入的 `candidate2` 这条边先放在一边，继续往下 `union()`。如果 `candidate2` 是红色的边，那么合并到最后，也不会出现任何异常，那么 `candidate2` 就是红色的边，即找到了要删除的边了。如果合并到最后出现了环的问题了，那说明 `candidate2` 是黑色的边，`candidate1` 才是红色的边，那么 `candidate1` 是要删除的边。
• 再来看看情况 1。如果一路合并到结束也没有发现出现入度为 2 的情况，那么说明遇到了情况 1 。情况 1 会出现环的情况。题目中说如果要删除边，就删除最后出现的那条边。具体实现见代码注释
You can’t perform that action at this time.