dunkelheit reference

dkh.datastructure.unionfind

  • UnionFind

    Declaration

    struct UnionFind;

    UnionFind (Disjoint Set Union)

    Examples

    1. import std.algorithm : equal, sort; auto uf = UnionFind(5); assert(!uf.same(1, 3)); assert(uf.same(0, 0)); uf.merge(3, 2); uf.merge(1, 1); uf.merge(4, 2); uf.merge(4, 3); assert(uf.count == 3); assert(uf.id[2] == uf.id[3]); assert(uf.id[2] == uf.id[4]); assert(equal(uf.group(0), [0])); assert(equal(uf.group(1), [1])); assert(equal(sort(uf.group(2).dup), [2, 3, 4])); auto cnt = 0; foreach (i; 0..5) { if (!uf.isLeader(i)) continue; cnt += uf.group(i).length; } assert(cnt == 5); // view all element exactly once

    • count

      Declaration

      size_t count;

      group count

    • this

      Declaration

      this(size_t n);

      Parameters

      size_t n

      # of element

    • merge

      Declaration

      void merge(size_t a, size_t b);

      merge a, b

    • group

      Declaration

      const const(int[]) group(size_t i);

      elements that are same group with i

    • isLeader

      Declaration

      const bool isLeader(size_t i);

      i がグループのリーダーか返す. 各グループにはただ1つのみリーダーが存在する

    • same

      Declaration

      const bool same(size_t a, size_t b);

      Are a and b same group?