1
class Solution {
2
 public:
3
  /*
4
  There are two cases for the tree structure to be invalid.
5
  1) A node having two parents;
6
  2) A circle exists
7

8
  If there are both invalid conditions, which means there is a node which has 2
9
  parents and there is also a circle even after we invalid edgeB. In this case,
10
  we have to return edgeA. only in this way can we avoid both double parents and
11
  circle for the tree.
12
  */
13

14
  int find(vector<int> &par, int n) {
15
    if (par[n] == n || par[n] < 0) return n;
16
    par[n] = find(par, par[n]);
17
    return par[n];
18
  }
19

20
  void findSpecialEdge(vector<vector<int>> &edges, vector<int> &edgeA, vector<int> &edgeB) {
21
    int len = edges.size();
22
    vector<int> par(len + 1, 0);
23
    for (vector<int> e : edges) {
24
      int p = e[0], c = e[1];
25
      if (par[c]) {
26
        edgeA = {par[c], c};
27
        edgeB = e;
28
        return;
29
      } else {
30
        par[c] = p;
31
      }
32
    }
33
  }
34

35
  vector<int> findRedundantDirectedConnection(vector<vector<int>> &edges) {
36
    int len = edges.size();
37
    vector<int> parent(len + 1, 0);
38
    for (int i = 0; i <= len; i++) parent[i] = i;
39

40
    vector<int> edgeA = {}; // 1st candidate
41
    vector<int> edgeB = {}; // 2nd candidate
42
    findSpecialEdge(edges, edgeA, edgeB);
43

44
    for (vector<int> e : edges) {
45
      int n1 = e[0];
46
      int n2 = e[1];
47
      if (edgeB.size() > 0 && (edgeB[0] == n1 && edgeB[1] == n2)) { // invalidate edgeB
48
        continue;
49
      }
50
      int p1 = find(parent, n1);
51
      int p2 = find(parent, n2);
52
      if (p1 == p2) { // circle found
53
        if (edgeB.size() > 0) {
54
          return edgeA;
55
        } else {
56
          return e;
57
        }
58
      } else {
59
        parent[p2] = p1;
60
      }
61
    }
62
    return edgeB;
63
  }
64
};