A review of all solutions

• This is same as graph valid tree.

1. O(n+e) DFS
``````void dfs(int from, int to, vector<bool>&vstd, vector<vector<int>> &adjlst)	{
if(vstd[to]) return;
vstd[to] = 1;
}
int countComponets(int n, vector<pair<int,int>>&edges) {
for(auto &e:edges) {
}
vector<bool> vstd(n);
int count = 0;
for(int i=0;i<n;i++) {
if(vstd[i]) continue;
count++;
}
return count;
}
``````
1. O(n+e) BFS
``````int bfs(int n, vector<pair<int,int>>&edges) {
for(auto &e:edges) {
}
vector<bool> vstd(n);
int count = 0;
for(int i=0;i<n;i++) {
if(vstd[i]) continue;
count++;
queue<int> q({i});
while(!q.empty()) {
int t = q.front();
q.pop();
if(vstd[t]) continue;
vstd[t] = 1;
q.push(nb);
}
}
}
return count;
}
``````
1. O(n+elg*n)union find
``````int root (int i, vector<int> &parent) {
while(parent[i]!=i) i=parent[i]=parent[parent[i]];
return i;
}
int unionFind(int n, vector<pair<int,int>>&edges) {
vector<int> parent(n),sz(n,1);
iota(parent.begin(),parent.end(),0);
for(auto &e:edges) {
int r0 = root(e.first,parent), r1 = root(e.second,parent);
if(r0==r1) continue;
n--;
if(sz[r0]<sz[r1]) {
parent[r0]=r1;
sz[r1]++;
} else {
parent[r1]=r0;
sz[r0]++;
}
}
return n;
}
``````

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