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

1 import std.algorithm : equal, sort;
2 auto uf = UnionFind(5);
3 assert(!uf.same(1, 3));
4 assert(uf.same(0, 0));
5 
6 uf.merge(3, 2);
7 uf.merge(1, 1);
8 uf.merge(4, 2);
9 uf.merge(4, 3);
10 
11 assert(uf.count == 3);
12 assert(uf.id[2] == uf.id[3]);
13 assert(uf.id[2] == uf.id[4]);
14 assert(equal(uf.group(0), [0]));
15 assert(equal(uf.group(1), [1]));
16 assert(equal(sort(uf.group(2).dup), [2, 3, 4]));
17 
18 auto cnt = 0;
19 foreach (i; 0..5) {
20     if (!uf.isLeader(i)) continue;
21     cnt += uf.group(i).length;
22 }
23 assert(cnt == 5); // view all element exactly once

UnionFind

Constructors

Members

Functions

Variables

Examples

Meta

Source