1
class UnionFind {
2
 public:
3
  int *parent;
4
  int *rank;
5

6
  UnionFind(int n) {
7
    rank = new int[n];
8
    parent = new int[n];
9

10
    for (int i = 0; i < n; i++) {
11
      parent[i] = i;
12
      rank[i] = 0;
13
    }
14
  }
15

16
  // collapsing find
17
  int Find(int node) {
18
    // if parent of node is itself
19
    if (parent[node] == node) {
20
      return node;
21
    }
22
    return parent[node] = Find(parent[node]);
23
  }
24

25
  // union by rank
26
  void Union(int u, int v) {
27
    // find the parent nodes of u and v
28
    u = Find(u);
29
    v = Find(v);
30

31
    // if u and v don't belong to the same set
32
    if (u != v) {
33
      if (rank[u] < rank[v]) {
34
        swap(u, v);
35
      }
36

37
      // attaching the lower rank tree with the higher rank one
38
      parent[v] = u;
39

40
      // if ranks are equal increase the rank of u
41
      if (rank[u] == rank[v]) {
42
        rank[u]++;
43
      }
44
    }
45
  }
46
};
47

48
class Solution {
49
 public:
50
  vector<int> findRedundantConnection(vector<vector<int>> &edges) {
51
    UnionFind UF = UnionFind(1001);
52

53
    for (vector<int> &edge : edges) {
54
      int u = edge[0];
55
      int v = edge[1];
56

57
      // if adding this edge creates a cycle
58
      if (UF.Find(u) == UF.Find(v)) {
59
        return {u, v};
60
      }
61

62
      // add u and v to the same set
63
      UF.Union(u, v);
64
    }
65

66
    // if no cycle was found
67
    return {-1};
68
  }
69
};