AC C Union-Find solution


  • 0
    E

    It works like Kruskal algorithm, wherever you detect an circle the graph is not an valid tree. And we should check the graph' nodes are all connected at the end.

    int find(int *set ,int target){
        int p = target;
        while(p!=set[p]) p = set[p];
        return p;
    }
    
    void unite(int *set , int p,int q){
        int pp = find(set,p);
        int qq = find(set,q);
        
        if(pp == qq) return;
        
        set[pp] = qq;
    }
    
    int connected(int *set ,int p,int q){
        return (find(set,p) == find(set,q));
    }
    
    int validTree(int n, int** edges, int edgesRowSize, int edgesColSize) {
        int set[n];
        for(int i = 0 ; i < n ; i++){
            set[i] = i;
        }
        for(int i = 0 ; i < edgesRowSize ;i++){
            int x = edges[i][0];
            int y = edges[i][1];
            if(connected(set,x,y)) return 0;
            else unite(set,x,y);
        }
        int root = find(set,0);
        for(int i = 0 ; i < n ; i++){
            if(find(set,i) != root) return 0;
        }
       
        return 1;
    }
    

Log in to reply
 

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