Union-Find
まずclassについて知っておかないと、何書いてるかわからない。 Union-Findはグループを
まとめる
同じかどうか判定する
の作業がすごい速さでできます。いいね。辺をつなげていく、とかグループをまとめていく、みたいな問題に使えるよ。
というわけでUnion-Findのclassです。サイズも測れるよ。
code:union-find.cpp
class UnionFind {
// まとめる 判定 サイズを知る
public:
// Aから見た親の番号を格納する。rootだったら-1*その集合のサイズ。
vector<int> Parent;
// 初期化
UnionFind(int N) {
Parent = vector<int>(N, -1);
}
// Aのrootを調べる
int root(int A) {
if (ParentA < 0) return A; // マイナスならそれはroot return ParentA = root(ParentA); }
// rootの値をプラスに戻して返す(サイズ)
int size(int A) {
}
// くっつける関数
bool connect(int A, int B) {
// AとBのroot同士をくっつける
A = root(A); // ここのAは、"rootの場所"の意味
B = root(B);
if (A == B) return false; // 既にくっついている
if (size(A) < size(B))
swap(A, B); // 大きい方にくっつけるために中身交換
ParentA += ParentB; // 中身更新 return true;
}
};