Disjoint set with path compression, C++

• disjoint set is designed to solve union-find problem.
It is very fast when applied with path compression.

``````class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
int N = M.size();
if (N == 0)
return 0;

d.resize(N);
for (int i = 0; i < N; ++i)
d[i] = i;

for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (M[i][j] == 1)
merge(i, j);

int count = 0;
for (int i = 0; i < N; ++i)
if (i == d[i])
count ++;
return count;
}

void merge(int i, int j)
{
d[parent(i)] = parent(j);
}

int parent(int x)
{
if (d[x] == x)
return x;
return d[x] = parent(d[x]); // path compression
}

vector<int> d;  // disjoint set
};
``````

• Hi, your code is simple and easy to understand! except this line

``````return d[x] = parent(d[x]); // path compression
``````

Could you help to explain? Thanks!

• @Datochi
find the topmost parent, and assign it to all the descendants in the path, so that the path is shorter(compressed).

before:
1->2
2->2
3->1
4->3
5->4
2 is the topmost parent.

after parent(5) called:
1->2
2->2
3->2
4->2
5->2
now all descendants in the path point to 2

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