The traditional implementation of union find tree (aka disjoint set) utilizes rank compression — this is the code with it.
int parent[1000], rank[1000];
int find(int x){
return parent[x] = (parent[x] == x ? x : find(parent[x]));
}
void Union(int p, int q){
p = find(p);
q = find(q);
if(rank[p] < rank[q]) parent[p] = q;
else parent[q] = p;
if(rank[p] == rank[q]) rank[p]++;
}
But in competitive programming, I found out that the rank compression was useless. Without rank compression, the code was shorter, and even the program ran faster. This is my implementation without rank compression.
int parent[1000];
void Union(int p, int q){ parent[find(p)] = find(q); }
and for some cases, I found implementing rank compression is quite hard (maybe impossible).
I will give you a sample problem : "Given a tree T, you should process Q queries — "paint the edge's value into x (>0) from path s to e".
I reversed the query, broke down the path s — e to s — LCA(s,e) — e, and used this algorithm to paint the tree. (root_val[s] : value of edge s — parent(s), dep[s] = depth of s. nxt[s] = parent(s))
int paint(int s, int e, int x){
if(dep[s] <= dep[e]) return s;
if(!root_val[s]) root_val[s] = x;
return nxt[s] = paint(nxt[s],e,x);
}
All of those program ran very fast in practice, but I was curious about the worst-case runtime of such path compression without ranks, so I googled for a while but didn't find any answer. Here's my question:
- Does the path compression runs in (amortized) sublinear time per query?
- If it doesn't, is there any counterexamples for that?