C++ Simple Class::UnionFind template


  • 0
    W
    class UnionFind{
            private:
                int count=0;
                vector<int> rank, parent;
            public:
             UnionFind(int n){
                 count = n;
                 rank = vector<int>(n,0);
                 for(int i = 0 ; i < n ; ++i){
                     parent.push_back(i);
                 }
             }
            int find(int ele){
                while(parent[ele]!=ele){
                    parent[ele] = parent[parent[ele]]; 
                    ele = parent[ele];
                }
                return ele;
            }
            int getCount(){
                return count;
            }
            void Union(int x, int y){
                int px = find(x);
                int py = find(y);
                if(px==py)
                    return;
                if(rank[px]>=rank[py]){
                    if(rank[px]==rank[py])
                        rank[px]++;
    
                    parent[py]=px;  
                }
                else
                    parent[px]=py;
                    
                count--;
            }
            
        };
    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& M) {
            int stu = M.size();
            if(stu==0)
                return 0;
            UnionFind un(stu);
            for(int i = 0 ;i<stu-1;++i)
                for(int j = i+1 ; j < stu ;++j)
                    if(M[i][j]==1)
                        un.Union(i,j);
                
            return un.getCount();
        }
    };
    

    feel free to ask question~


Log in to reply
 

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