Union find tree without ranks

Revision en1, by ko_osaga, 2015-11-08 06:51:42

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?
2. If it doesn't, is there any counterexamples for that?

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 ko_osaga 2015-11-08 07:58:52 10 Tiny change: 'inear time?\n2. If i' -> 'inear time per query?\n2. If i'
en1 ko_osaga 2015-11-08 06:51:42 1770 Initial revision (published)