snsokolov's blog

Disjoint set union (DSU)
By snsokolov, history, 9 years ago, In English

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); }
};
  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It works O(log N);

Also you can add heuristic by height to get O(a(N)), where a(N) is Ackermann inverse function

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)).

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ))

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Curious, is there any faster DSU implementation for N < 10^6?

→ Reply