24ms C++ solution


  • 0
    R
    class Solution {
    public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        if(edges.size()>=n||(edges.empty()&&n>1)) return false;  //if the number of edges>=the number of nodes, it means there is a loop in this graph
        if(edges.empty()&&n<=1) return true; //empty tree or one node tree;
        deque<pair<int,int>> deq;
        vector<set<int>> res = {{edges[0].first, edges[0].second}};
        int pn = 2;
        for(int i=1;i<=edges.size()-1;++i)
            deq.push_back(edges[i]);
            
        while(!deq.empty()){
            bool insert_big = false;
            int sz = deq.size();
            while(sz!=0){
                int u = deq.front().first, v = deq.front().second;
                bool insert_sml = false;
                --sz;
                for(int j=0;j<=res.size()-1;++j){
                    set<int>& s_tp = res[j];
                    if(s_tp.find(u)!=s_tp.end()&&s_tp.find(v)!=s_tp.end()){
                        deq.pop_front();
                        insert_sml = true;
                        insert_big = true;
                        break;
                    }
                    else if(s_tp.find(u)!=s_tp.end()||s_tp.find(v)!=s_tp.end()){
                        if(s_tp.find(u)!=s_tp.end()) s_tp.insert(v);
                        if(s_tp.find(v)!=s_tp.end()) s_tp.insert(u);
                        ++pn;
                        deq.pop_front();
                        insert_sml = true;
                        insert_big = true;
                        break;
                    }
                }
                if(!insert_sml){
                    pair<int,int> cur = deq.front();
                    deq.pop_front();
                    deq.push_back(cur);
                }
            }
            if(!insert_big&&res.size()==1)return false; //it points out there is more than one tree in this graph
        }
        if(n-pn+res.size()!=1) return false;    // it points out that there are single nodes although there is only one tree
        return true;
        }
    };

Log in to reply
 

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