Classic C++ Union-Find solution


  • 0
    R

    Using topological sort to find a circle then use set to find if there is more then one tree seems to be a faster sol, but this is just a classic C++ Union-Find approach, if some one is interested to know.

    class Solution {
    public:
        class node{
        public:
            node(int a) : val(a), parent(&(*this)){}
            int val;
            node* parent;
        };
        node* find(node* a){
            while(a->parent != a){
                a = a->parent;
            }
            return a;
        }
        
        bool join(node* a, node* b){
            node* x = find(a);
            node* y = find(b);
            //cout << x->val << y->val;
           if(x == a && y == a){
               return false;
           }
           if(x == b && y == b){
               return false;
           }
            
            if(x == a){
                x->parent = y;
                return true;
            }
            if(y == b){
                
                y->parent = x;
                return true;
            }
            if(x != y){
                x->parent = y;
                return true;
            }
            return false;
    
        }
        
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(edges.empty()){
                if(n == 1){
                    return true;
                }
                return false;
            }
            map<int, node*> m;
            for(int i = 0; i < n; i++){
                node* a = new node(i);
                m[i] = a;
            }
            for(int i = 0; i < (int)(edges.size()); i++){
                
                
                if(!join(m[edges[i].first], m[edges[i].second])){
                    return false;
                }
            }
            set<node*> s;
            for(int i = 0; i < n; i++){
                s.insert(find(m[i]));
            }
           // cout << 123;
            return s.size() == 1 ? true : false;
            
        }
    };

Log in to reply
 

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