Note that there is a path compression in the find function.
The time complexity of one operation in UnionFind with N elements and path compression only is amortized O(logN).
class UnionFind {
vector<int> id;
public:
UnionFind(int n) : id(n) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
id[find(a)] = find(b);
}
bool connected(int a, int b) {
return find(a) == find(b);
}
};
Get Size of Union
We can use a size array to keep track of the size of each union.
cnt keeps track of the number of unions.
class UnionFind {
vector<int> id, size;
int cnt;
public:
UnionFind(int n) : id(n), size(n, 1), cnt(n) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
id[x] = y;
size[y] += size[x];
--cnt;
}
bool connected(int a, int b) { return find(a) == find(b); }
int getSize(int a) { return size[find(a)]; }
int getCount() { return cnt; }
};
Merge using Rank
The time complexity of one operation in UnionFind with N elements, path compression and union by rank is amortized O(alpha(N)) where alpha(N) is the inverse function of Ackermann function. Note that O(alpha(N)) is even more efficient than O(logN).
class UnionFind {
vector<int> id, rank;
int cnt; // `cnt` is the number of connected components in the graph
public:
UnionFind(int n) : id(n), rank(n, 0), cnt(n) {
iota(begin(id), end(id), 0);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
void connect(int i, int j) {
int p = find(i), q = find(j);
if (p == q) return;
if (rank[p] > rank[q]) id[q] = p; // always use the node with GREATER rank as the root
else {
id[p] = q;
if (rank[p] == rank[q]) rank[q]++;
}
--cnt;
}
bool connected(int i, int j) { return find(i) == find(j); }
int getCount() { return cnt; }
};
Problems
Static Connection
Dynamic Connection
Involves multiple steps to build the connection gradually.
Back in Time
Since Union Find can only BUILD connection gradually, when we see problems that BREAK connection gradually with multiple steps, we can traverse the steps in reverse order so as to BUILD the connections gradually.
