Redundant Connection

1class Solution {
2    public int[] findRedundantConnection(int[][] edges) {
3        int n = edges.length;
4        int[] parent = new int[n + 1];
5        int[] size = new int[n + 1];
6
7        for (int i = 1; i <= n; i++) {
8            parent[i] = i;
9            size[i] = 1;
10        }
11
12        for (int[] edge : edges) {
13            int u = edge[0], v = edge[1];
14
15            int rootU = find(parent, u);
16            int rootV = find(parent, v);
17
18            if (rootU == rootV) {
19                return edge;
20            }
21
22            union(parent, size, rootU, rootV);
23        }
24
25        return new int[]{};
26    }
27
28    private int find(int[] parent, int x) {
29        if (parent[x] != x) {
30            parent[x] = find(parent, parent[x]);
31        }
32        return parent[x];
33    }
34
35    private void union(int[] parent, int[] size, int x, int y) {
36        if (size[x] < size[y]) {
37            parent[x] = y;
38            size[y] += size[x];
39        } else {
40            parent[y] = x;
41            size[x] += size[y];
42        }
43    }
44}