leetcode/0685.Redundant-Connection-II/README.md
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:
在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。输入一个有向图，该图由一个有着 N 个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组。 每一个边的元素是一对 [u, v]，用以表示有向图中连接顶点 u and v 和顶点的边，其中父节点 u 是子节点 v 的一个父节点。返回一条能删除的边，使得剩下的图是有 N 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
注意:
rank() 优化，这些优化会改变有向边原始的方向。所以并查集只需要记录 parent() 就够用了。union() 时，加入一条边以后，会使一个节点的入度变成 2，那么记录下这两条边为 candidate1 和 candidate2。将后加入的 candidate2 这条边先放在一边，继续往下 union()。如果 candidate2 是红色的边，那么合并到最后，也不会出现任何异常，那么 candidate2 就是红色的边，即找到了要删除的边了。如果合并到最后出现了环的问题了，那说明 candidate2 是黑色的边，candidate1 才是红色的边，那么 candidate1 是要删除的边。