RedundantConnection.java

public class RedundantConnection {
    private int[] parents;

    public int[] findRedundantConnection(int[][] edges) {
        int N = edges.length;
        parents = new int[N + 1];  // # of nodes
        for (int i = 0; i < N + 1; i++) {
            parents[i] = i;
        }

        return findRedundant(edges);
    }

    // Use Union Find to find redundant edge
    public int[] findRedundant(int[][] edges) {
        for (int[] edge : edges) {
            boolean res = union(edge[0], edge[1]);
            if (!res) return edge;
        }
        return null;
    }

    public boolean union(int x, int y) {
        int xP = findParent(x);
        int yP = findParent(y);
        if (xP == yP) return false;
        parents[yP] = xP;
        return true;
    }

    public int findParent(int x) {
        while (parents[x] != x)
            x = parents[x];
        return x;
    }
}