Lib/UnionfFind
できること
ある2要素を結合する
ある2要素が連結か判定する
ある要素と連結な要素の大きさを判定する
code:cpp
struct UnionFind {
vector< int > data; //負ならサイズ 正なら親ノード
UnionFind(int sz) {
data.assign(sz, -1);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if(x == y) return (false);
if(datax > datay) swap(x, y); //Xの方が大きい状態にする return (true);
}
int find(int k) {
if(datak < 0) return (k); return (datak = find(datak)); }
int size(int k) {
}
bool same(int x,int y){
return find(x) == find(y);
}
};
できないこと
重み付きuf
書いてもいいけど……