1
class Solution {
2
  public int[] findRedundantConnection(int[][] edges) {
3
    UnionFind uf = new UnionFind(edges.length);
4
    for (int[] edge : edges) {
5
      if (!uf.union(edge[0], edge[1])) {
6
        return new int[] {edge[0], edge[1]};
7
      }
8
    }
9
    return null;
10
  }
11

12
  private class UnionFind {
13
    int[] rank;
14
    int[] root;
15

16
    UnionFind(int n) {
17
      rank = new int[n + 1];
18
      root = new int[n + 1];
19
      for (int i = 1; i <= n; i++) {
20
        root[i] = i;
21
        rank[i] = 1;
22
      }
23
    }
24

25
    int find(int x) {
26
      if (x == root[x]) {
27
        return x;
28
      }
29
      return root[x] = find(root[x]);
30
    }
31

32
    boolean union(int x, int y) {
33
      int rootX = find(x);
34
      int rootY = find(y);
35
      if (rootX != rootY) {
36
        if (rank[rootX] > rank[rootY]) {
37
          root[rootY] = root[rootX];
38
        } else if (rank[rootY] > rank[rootX]) {
39
          root[rootX] = root[rootY];
40
        } else {
41
          root[rootY] = root[rootX];
42
          rank[rootX]++;
43
        }
44
        return true;
45
      }
46
      return false;
47
    }
48
  }
49
}