# Union-Find based Concise C++ solution refereed to @CNN_Boost

• This problem is a standard Union-Find problem, so we can first implement a union-find by ourself, then we can just add edges to the Union-set and update the father information.
Of course, there are many different implementation variation of the Union-Find, but the key opration is 2, one is to find the parent info, the other is to union the father of 2 nodes.

Here is a C++ implementation :

``````class Solution {

private:
class UnionFind {
public:
UnionFind(const int n) : set_(n), count_(n) {
/** fills the vector value from 0 and increase by 1 element by element **/
iota(set_.begin(), set_.end(), 0);
}
/** get the parents of the current node & compress the path along the way**/
int find_set(const int x) {
if(set_[x] != x) {
set_[x] = find_set(set_[x]);
}
return set_[x];
}
/** combine the 2 node to have the same parent node **/
void union_set(const int x, const int y) {
int x_root = find_set(x), y_root = find_set(y);
if(x_root != y_root) {
set_[min(x_root, y_root)] = max(x_root, y_root);
--count_;
}
}
int size() const {
return count_;
}
private:
/** record the parent info path **/
vector<int> set_;
/** record the connected component count **/
int count_;
};
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
UnionFind union_find(n);
for(const auto& e : edges) {
union_find.union_set(e.first, e.second);
}
return union_find.size();
}
};``````

• Here is a much shorter and clean C++ implementations :

``````  class Solution {
vector<int> roots;
int findRoot(int idx) {
while(idx != roots[idx]) {
roots[idx] = roots[roots[idx]];
idx = roots[idx];
}
return idx;
}
public:
int countComponents(int n, vector<pair<int, int>>& edges) {
int result = n;
roots.resize(n, 0);
iota(roots.begin(), roots.end(), 0);
for(const auto& e : edges) {
int root1 = findRoot(e.first);
int root2 = findRoot(e.second);
if(root1 != root2) {
roots[root1] = root2;
--result;
}
}
return result;
}
};``````

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