Can you explain the find function in the Union Find Disjoint Set data structure?

Revision en1, by vikalp14, 2018-10-07 10:48:10

// 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]))

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English vikalp14 2018-10-07 12:25:04 24
en2 English vikalp14 2018-10-07 12:22:45 93
en1 English vikalp14 2018-10-07 10:48:10 1532 Initial revision (published)