684. Redundant Connection

Link

Solution

  public int[] findRedundantConnection(int[][] edges) {
        int[] parents = new int[2001];
        for(int i = 0; i < 2001; i++){
            parents[i] = i;
        }
        
        for(int[] edge : edges){
            int from = edge[0], to = edge[1];
            if(find(parents, from) == find(parents, to)){
                return edge;
            }
            union(parents, from, to);
        }
        return null;
    }
    
    private int find(int[] parents, int node){
        if(node == parents[node])
            return node;
        else
            return find(parents, parents[node]);
    }
    
    private void union(int[] parents, int from, int to){
        int fromRoot = find(parents, from);
        int toRoot = find(parents, to);
        parents[toRoot] = fromRoot;
    }