Data Structure: Union Find - cocoder39/coco39_LC GitHub Wiki
time complexity: if m operations, either Union or Find, applied to n elements, the total run time is O(mlog*n), where log* is the iterated logarithm
ppt from Princeton U : https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf
class UnionFind {
public:
UnionFind (const int N) {
for (int i = 0; i < N; i++)
id.push_back(i);
sz.push_back(1);
}
bool connected (const int p, const int q) {
return root(p) == root(q);
}
void union_ (const int p, const int q) {
int i = root(p);
int j = root(q);
if(i == j) return;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
}
else{
id[j] = i;
sz[i] += sz[j];
}
}
private:
vector<int> id;
vector<int> sz;
int root (int i) {
//lg* N ~= O(1), number of times take lg N to 1. less than 5 in real world
while (i != id[i]) { // i == id[i] iff i is a root
//make every other node in path points to its grandparent
//flat the tree during finding root
id[i] = id[id[i]];
i = id[i];
}
return i;
}
};