vikalp14's blog

By vikalp14, history, 4 years ago, In English

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you format your code properly?