684. Redundant Connection

class Solution {
    private static class UnionFind {

        private final int[] parent;

        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int getRoot(int x) {
            if (x != parent[x]) { // 使用递归压缩时此处为 if
                parent[x] = getRoot(parent[x]); // path compression
            }

            return parent[x];
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x), yRoot = getRoot(y);
            parent[xRoot] = yRoot;
        }

    }

    public int[] findRedundantConnection(int[][] edges) {
        UnionFind unionFind = new UnionFind(edges.length);
        for (int[] edge : edges) {
            int nodeA = edge[0] - 1, nodeB = edge[1] - 1;
            if (unionFind.getRoot(nodeA) != unionFind.getRoot(nodeB)) {
                unionFind.union(nodeA, nodeB);
            } else {
                // nodeA 与 nodeB 已经处于连通状态，当前边是多余的
                return edge;
            }
        }

        return new int[0];
    }
}

References

684. Redundant Connection
剑指 Offer II 118. 多余的边