Concise JAVA solution, 4ms


  • -1

    Edge(i,j) should be removed if

    1. j is a child of another node ( j != root[j] )
    2. i and j form a ring ( root[i] == root[j] )
    3. If both of that two edges exists, the result is the unique edge which makes up the ring and has duplicate parent nodes.
        public int[] findRedundantDirectedConnection(int[][] edges) {
            int[] ancestor = new int[edges.length + 1];
            int[][] res = new int[2][2];
            for(int[]node : edges) {
                if(node[1] != getAncestor(ancestor, node[1]))
                    res[0] = node;
                else if(getAncestor(ancestor, node[0]) == getAncestor(ancestor, node[1]))
                    res[1] = node;
                else
                    ancestor[node[1]] = ancestor[node[0]];
                if(res[0][0] != 0 && res[1][0] != 0)
                    return find(edges, ancestor, res[0], res[1]);
            }
            return res[0][0] == 0 ? res[1] : res[0];
        }
        
        public int getAncestor(int[] ancestor, int node) {
            if(node != ancestor[node])
                ancestor[node] = ancestor[node] == 0 ? node : getAncestor(ancestor, ancestor[node]);
            return ancestor[node];
        }
        
        public int[] find(int[][] edges, int[] ancestor, int[] removed0, int[] removed1) {
            for(int[] res : edges)
                if(res[1] == removed0[1] && getAncestor(ancestor, res[1])  == getAncestor(ancestor, removed1[1]))
                    return res;
            return new int[2];
        }
    
    

  • 0
    W

    @SaoBiaoZi

    Can you try your solution on this test case:

    [[2,1],[3,1],[4,2],[1,4]]

    It seems your answer is [3,1] while expected answer is [2,1].

    Please correct me if I am wrong.


  • 0

    @wzypangpang I found that. Updated. Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.