Union-Find
Union-Find Disjoint Set, 互いに素な集合に対するデータ構造
Outline
いくつかの互いに素な集合において、指定した要素がどの集合に含まれるかを求める.
もしくは、指定した二つの要素が同じ集合に含まれるか調べる.
Floyd-Warshall?による推移閉方でも同じようなことが分かるが、 Floyd-Warshall?はまず最初に推移閉包を適用して、出力は入力を添え字として配列の値を出すだけのような場合に有効である.
それに対してUnion-Find?は、入力の合間に出力が必要な時などに使う.
Program
#define
class UnionFind {
private:
int p[_UFDS_MAX], rank[_UFDS_MAX];
int max_rank, n;
public:
void link(int x, int y) {
if(x != y) {
if(rank[x] > rank[y]) {
p[y] = x;
rank[x] += rank[y];
rank[y] = 0;
} else {
p[x] = y;
rank[y] += rank[x];
rank[x] = 0;
}
if(rank[x] > max_rank) {
max_rank = rank[x];
}
if(rank[y] > max_rank) {
max_rank = rank[y];
}
}
}
void make_set(int x) {
p[x] = x;
rank[x] = 1;
}
int find_set(int x) {
if(x != p[x]) {
p[x] = find_set(p[x]);
}
return p[x];
}
void union_set(int x,int y) {
link(find_set(x), find_set(y));
}
int get_max_numbers_in_set() {
return max_rank;
}
int get_numbers_of_set() {
int set_counter = 0;
for(int i = 1 ; i <= n ; i++) {
if(rank[i] != 0) {
set_counter++;
}
}
return set_counter;
}
bool is_connected(int x, int y) {
return find_set(x) == find_set(y);
}
void init(int n) {
this->n = n;
for(int i = 1 ; i <= n ; i++) {
make_set(i);
}
max_rank = 0;
}
};