24ms C++ solution

• ``````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;
}
};``````

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