# C++ SolutionDFS and Union Find version

• //DFS Version
class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
int ans = 0;
if(!n)
return ans;
if(!edges.size())
return n;
vector<bool> vis(n);
unordered_map<int,unordered_set<int>> mp;
for(int i = 0; i < edges.size(); ++ i){
mp[edges[i].first].insert(edges[i].second);
mp[edges[i].second].insert(edges[i].first);
}
for(int i = 0; i < n; ++ i){
if(!vis[i]){
++ ans;
dfs(i, vis, mp);
}
}
return ans;
}

private:
void dfs(int u, vector<bool> &vis, unordered_map<int,unordered_set<int>> &mp){
vis[u] = 1;
unordered_set<int>::iterator it = mp[u].begin();
for(; it != mp[u].end(); ++ it){
int v = *it;
if(!vis[v]){
dfs(v, vis, mp);
}
}
}

};

//Union Find Version
class Solution {
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
int ans = 0;
if(!n)
return ans;
if(!edges.size())
return n;
fa.resize(n);
for(int i = 0; i < n; ++ i)
fa[i] = -1;

ans = n;
for(int i = 0; i < edges.size(); ++ i){
if(find(edges[i].first) != find(edges[i].second)){
-- ans;
unionedge(edges[i].first, edges[i].second);
}
}

return ans;
}

int find(int u){
int s = u;
for(; fa[s] >= 0; s = fa[s]) ;
while(u != s){
int tmp = fa[u];
fa[u] = s;
u = tmp;
}
return s;
}

void unionedge(int a, int b){
int f1 = find(a), f2 = find(b);
int sumf = fa[f1] + fa[f2];
if(fa[f1] <= fa[f2]){
fa[f2] = f1;
fa[f1] = sumf;
}else{
fa[f1] = f2;
fa[f2] = sumf;
}
}

private:
vector<int> fa;
};

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