### vikalp14's blog

By vikalp14, history, 5 years ago, // Union-Find Disjoint Sets Library written in OOP manner, using both path compression and union by rank heuristics
class UnionFind {                                              // OOP style
private:
vi p, rank, setSize;                       // remember: vi is vector<int>
int numSets;
public:
UnionFind(int N) {
setSize.assign(N, 1);
numSets = N;
rank.assign(N, 0);
p.assign(N, 0); for (int i = 0; i < N; i++) p[i] = i; }

int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }

bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }

void unionSet(int i, int j) {
if (!isSameSet(i, j)) {
numSets--;
int x = findSet(i), y = findSet(j);
// rank is used to keep the tree short
if (rank[x] > rank[y]) {
p[y] = x;
setSize[x] += setSize[y]; }
else {
p[x] = y;
setSize[y] += setSize[x];
if (rank[x] == rank[y])
rank[y]++; }}}

int numDisjointSets() { return numSets; }
int sizeOfSet(int i) { return setSize[findSet(i)]; }
};



What I could infer: find funtion gives the key of a particular set. we are setting p[i]=find(p[i]), this will set the key of the set as parent of every element of the set.

Doubt: Some elements will still have p[i]=nk where nk is an element of the set which is not the key. If this is the case ,then why perform this assignment (p[i]=find(p[i])) Comments (1)
| Write comment?
 » Can you format your code properly?