UnionFind

abc120-d問題を解きました。union-find木を使うそう

上記の解説を参考に解いたけど、UnionFindの実装の理解に少し時間がかかったので、整理

初期値を-1にする理由とかの

以下はコードにコメントで自分の理解を追加したもの

code: unionfind.cpp

struct UnionFind {

// parで親のnode値と、サイズを同時に管理する。

// 根ではないnodeのparは親となるnodeの値が入ってる

// 根にはサイズ数が入っている。区別できるようにサイズはマイナスの値で入っている

// そのため、初期値はすべて-1になる(mergeの際にmergeされる側の根に、mergeする方の根が加算される

vector<int> par;

UnionFind(int n) : par(n, -1) { }

void init(int n) { par.assign(n, -1); }

int root(int x) {

// 上記の通り,負の値ということは、根である

}

bool merge(int x, int y) {

x = root(x); y = root(y);

if (x == y) return false;

// サイズが大きいほうにマージする

// 以下は必ずxが大きいほう(サイズはマイナスの値が入ってるので)にするように調整している

// xのサイズに、yのサイズを加算する

// yの根をxに更新する

return true;

}

bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す

int rx = root(x);

int ry = root(y);

return rx == ry;

}

int size(int x) {

}

};

実際にUnionFindが更新されていく様子を図にしてみた

Node数が7で考える

https://gyazo.com/65d8010718add8233ba0cab7d619c85a

1-4をつなぐ辺を入れてみることを考える。merge関数が呼ばれる

https://gyazo.com/01342a5bc48495f129d92ba735b452be

サイズは同じ1なので、xに指定されたindex:1が親となる

https://gyazo.com/9ef797181b0f3d310093e4c2f2e8f7a9

https://gyazo.com/be447fb31a48fd4e604a91287f3f6c32

https://gyazo.com/ec8627f3073ba11427c18da6ab213405

https://gyazo.com/5649fff689de78dbe0a335d4fc37f55a

https://gyazo.com/ff7e543269d3bccd37329eef319358e5