For the 566D - Реструктуризация компании
Basic Disjoint Set C++ implementation (w/o ranks) using int vector
class DisjointSet{ public:
vector<int> parent;
DisjointSet(int n): parent(n) { for(int i=0; i<n; i++) parent[i] = i; }
void join(int a, int b) { parent[find(b)] = find(a); }
int find(int a){ return a == parent[a] ? a : parent[a] = find(parent[a]); }
bool check(int a, int b){ return find(a) == find(b); }
};
It works O(log N);
Also you can add heuristic by height to get O(a(N)), where a(N) is Ackermann inverse function
I know. But it has path compression heuristic, why would you think it is still runs LogN?
Also, I specifically removed the rank heuristic. In my tests it is only slows things down and duplicates the memory consumption. I may be wrong, but I think rank heuristic is not needed here.
DSU without any heuristics runs O(n), path zipping + ranking heuristics runs O(a(n)), and only zipping or only ranking heuristic will run O(log(n)).
Agree that only ranking heuristic will run logN. But for only zipping heuristic to be logN is not obvious to me. Do you know if there is an easy proof?
In my testing for size < 10^6 ranking or random-swap ranking addition is causing 20% slowdown ))
Curious, is there any faster DSU implementation for N < 10^6?