Блог пользователя snsokolov

Автор snsokolov, история, 9 лет назад, По-английски

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); }
};
  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It works O(log N);

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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