684. Redundant Connection

class DSU {
    int[] root;
    int[] size;

    public DSU(int n) {
        root = new int[n];
        size = new int[n];
        Arrays.fill(size, 1);
        
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        if (root[x] != x) {
            root[x] = find(root[x]);
        }

        return root[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;

        if (size[rootX] < size[rootY]) {
            root[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            root[rootY] = rootX;
            size[rootX] += size[rootY];
        }

        return true;
    }
}

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;

    DSU dsu = new DSU(n + 1);
    for (int[] e : edges) {
        if (!dsu.union(e[0], e[1])) return e;
    }

    return new int[0];
}