# 68ms in C++ by Union Find and BFS

• Background:

1. use a vector to save the possible node set. Firstly initialize the vector by the first edge pair.

2. set up a deque which is initialized by the elements of edges from index i to the last one.

3. in every loop, use deque.size() as the termination condition in order to traverse every elements of deque.

4. if either element in deque.front() is found in any set, add it
if not, pop edque.front() out and push it back to the tail of deque

`````` class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
if(edges.empty()||n==0) return n;
deque<pair<int,int>> deq;
vector<set<int>> res = {{edges[0].first, edges[0].second}};   //the node set
int pn = 2;   //the number of recorded node
for(int i=1;i<=edges.size()-1;++i)
deq.push_back(edges[i]);

while(!deq.empty()){
bool insert_big = false;  //to point out if there is no insertion in the whole traverse
int sz = deq.size();   //termination condition
while(sz!=0){
int u = deq.front().first;
int 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){
int u = deq.front().first;
int v = deq.front().second;
res.push_back({u,v});
pn = pn+2;
deq.pop_front();
}
}
return n-pn+res.size();
}
};``````

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