UnionFind

UnionFind (Disjoint Set Union)

struct UnionFind {

size_t count;

this(size_t n);

void merge(size_t a, size_t b);

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

bool isLeader(size_t i);

bool same(size_t a, size_t b);

}

Constructors

this this(size_t n)

Members

Functions

group const(int[]) group(size_t i): elements that are same group with i
isLeader bool isLeader(size_t i): i がグループのリーダーか返す. 各グループにはただ1つのみリーダーが存在する
merge void merge(size_t a, size_t b): merge a, b
same bool same(size_t a, size_t b): Are a and b same group?

Variables

count size_t count;: group count

Examples

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

UnionFind

Constructors

Members

Functions

Variables

Examples

Meta

Source