C++ Union Find solution 95% percentile


  • 0
    G
    class Solution {
        
        vector<int> UF;
        vector<int> Size;
        
        int Find(int V)
        {
            if(UF[V] == V)
            {
                return V;
            }
            
            UF[V] = Find(UF[V]);
            return (UF[V]);
        }
        
        bool Union(int V1, int V2)
        {
            int R1 = Find(V1);
            int R2 = Find(V2);
            
            if(R1 == R2)
            {
                return (false);
            }
            
            if(Size[R1] > Size[R2])
            {
                UF[R2] = R1;
                Size[R1] += Size[R2];
            }
            else
            {
                UF[R1] = R2;
                Size[R2] += Size[R1];
            }
            
            return (true);
        }
        
    public:
    
        bool validTree(int n, vector<pair<int, int>>& edges) 
        {
            UF.resize(n);
            Size.resize(n);
            
            for(int i = 0; i < UF.size(); ++i)
            {
                UF[i] = i;
                Size[i] = 1;
            }
            
            for(auto &e : edges)
            {
                if(Union(e.first,e.second) == false)
                {
                    return (false);
                }
            }
            
            int Count = 0;
            
            for(int i = 0; i < UF.size(); ++i)
            {
                if(UF[i] == i)
                {
                    Count++;
                }
                
                if(Count > 1)
                {
                    return (false);
                }
            }
            
            return (true);
        }
    };

Log in to reply
 

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