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:↵
↵
1. Does the path compression runs in (amortized) sublinear time per query?↵
2. If it doesn't, is there any counterexamples for that?
↵
↵
~~~~~↵
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:↵
↵
1. Does the path compression runs in (amortized) sublinear time per query?↵
2. If it doesn't, is there any counterexamples for that?
