685. Redundant Connection II

问题：

的第二版本，由原来的无向图->有向图

那么给定一组edge [u,v]，定义从顶点u到v的连线，构成有向图。parent[v]=u，u->v

求最后一个多余出来的[u,v]，使得出现了回环。（若没有这个连线，则可形成tree）

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

Example 3:
Input: [[2,1],[3,1],[4,2],[1,4]]
Output: [2,1]
Explanation: The given directed graph will be like this:
1 <- 2 
↑ ↘︎ ↑  
3    4 

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.

解法：并查集（Disjoint Set）

与无向图的区别：

父子关系明确

因此，要成为tree，除了不能形成环cycle之外，对每一个节点，还只能有一个parent节点。

例如，

Example的 1：节点3 就有两个parent：1 和 2 （[1,3], [2,3]）
Example的 2：节点1 就有两个parent：2 和 3 （[2,1], [3,1]）

所以，我们在原先无向图的求解之前，

增加判断parent节点个数的逻辑。

这里增加parent数组，表示每个节点的父节点。

⚠️ 注意：这里不是Disjoint Set类里的表示每个节点root的辅助变量。是本问题特殊增加。

遍历edges，对每个[u, v]，更新parent[v]=u

然后，在每次更新之前，判断是否parent[v]已经被赋值，若被赋值了，则我们要返回的最终结果，有可能是：

candidate_res1：之前赋值的那个边：[parent[v], v]
candidate_res2： or 当前的边：[u, v]

这里说明，节点v有两个parent。若两条边都在，那么一定不能构成tree。

然后，我们带着这两个可能的结果，去尝试和无向图一样的环cycle的判断逻辑。

我们先假设res2不正确，删除res2的边。去进行尝试。

若出现环：
- 证明我们删错了，结果应该是res1。
- or 刚才的parent判断中，根本没有出现一个节点有两个parent的情况，那么直接返回当前出现环的边。（和无向图的一样）
若没有出现环：
- 证明我们删对了，结果就是res2。

代码参考：

 1 class Solution {
 2 public:
 3     vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
 4         vector<int> candidate_res1, candidate_res2;
 5         vector<int> parent(edges.size(),-1);
 6         //find duplicated root point
 7         for(int i=0; i<edges.size(); i++) {
 8             int p1 = edges[i][0], p2 = edges[i][1];
 9             if(parent[p2-1] != -1) {//p2 has already had a parent
10                 candidate_res1 = {parent[p2-1], p2};
11                 candidate_res2 = {p1, p2};
12                 //delete res2
13                 edges[i][0] = -1;
14                 edges[i][1] = -1;
15                 break;
16             }
17             parent[p2-1]=p1;
18         }
19         DisjointSet DS(edges.size());
20         for(int i=0; i<edges.size(); i++) {
21             int p1 = edges[i][0], p2 = edges[i][1];
22             if(p1==-1 || p2==-1) continue;
23             if(false == DS.merge(p1-1, p2-1)) {//cycle is found
24                 return candidate_res1.empty()?edges[i]:candidate_res1;
25             }
26         }
27         return candidate_res2;
28     }
29 };

附：DisjointSet的代码参考：

 1 class DisjointSet {
 2 public:
 3     DisjointSet(int n):parent(n), rank(n, 0) {
 4         for(int i=0; i<n; i++) parent[i] = i;
 5     }
 6     int find(int i) {
 7         if(parent[i] != i) {
 8             parent[i] = find(parent[i]);
 9         }
10         return parent[i];
11     }
12     bool merge(int x, int y) {
13         int x_root = find(x);
14         int y_root = find(y);
15         if(x_root == y_root) return false;
16         if(rank[x_root] < rank[y_root]) {
17             parent[x_root] = y_root;
18         } else if(rank[y_root] < rank[x_root]) {
19             parent[y_root] = x_root;
20         } else {
21             parent[x_root] = y_root;
22             y_root++;
23         }
24         return true;
25     }
26 private:
27     vector<int> parent;
28     vector<int> rank;
29 };