LeetCode 685. Redundant Connection II

3 invalid situations

case1: 2 parents no circle

case2: 2 parents with circle

case3: 1 parent with circle

2 main steps

1 check whether there exists a node with 2 parents, if yes, store the two edges.

2 if no edge yielded from step 1, apply union-find and find the edge creating cycle (same as 684);

ELSE, apply union-find to ALL edges EXCEPT edges from step 1, then check: if edge 1 from step 1 creates a cycle, return edge 1; else return edge 2.

class Solution {
public:
    vector<int> parent;
    vector<int> rank;
    
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        vector<int> tree_parent(n+1,-1);
        vector<int> edge1{-1,-1}, edge2{-1,-1}; // parent1->child, parent2->child
        
        for (auto edge:edges){
            int n1=edge[0], n2=edge[1];
            if (tree_parent[n2]!=-1){
                edge1 = {tree_parent[n2],n2};
                edge2 = edge;
            }
            tree_parent[n2] = n1;
        }
        
        vector<int> res;
        parent.resize(n+1,-1);
        rank.resize(n+1,0);
        
        if (edge1[0]==-1){ // no node with two parents
            // union find by rank
            for (auto edge:edges){
                int n1=edge[0], n2=edge[1];
                if (Find(n1)!=Find(n2)) 
                    Union(n1,n2);
                else res = edge;
            }
        }else{
            // union find all edges except edge1 and edge2
            for (auto edge:edges){
                if (edge==edge1 || edge==edge2) continue;
                int n1=edge[0], n2=edge[1];
                if (Find(n1)!=Find(n2)) 
                    Union(n1,n2);
                else res = edge;
            }
            
            // if add edge1 cause a loop return edge1
            if (Find(edge1[0])==Find(edge1[1])) res=edge1;
            else res=edge2;
        }
        
        return res;
    }
    
    void Union(int x, int y){
        int rootx=Find(x), rooty=Find(y);
        if (rootx==rooty) return;
        if (rank[rootx]>rank[rooty]){
            parent[rooty] = rootx;
        }else if (rank[rootx]<rank[rooty]){
            parent[rootx] = rooty;
        }else{
            rank[rootx] += 1;
            parent[rooty] = rootx;
        }
    }
        
    int Find(int x){
        if (parent[x]<0) return x;
        return parent[x]=Find(parent[x]);
    }
};

时间复杂度：O(mα(n)) for m operations，amortized O(1) each operation

LeetCode 685. Redundant Connection II

相关推荐