b1u3 https://blog.hatena.ne.jp/b1u3/ いろんなことで四苦Hack（仮） https://b1u3.hateblo.jp/ 競技プログラミング 人間は愚か。えぬわいです。 qiita.com atcoder.jp Union-find木の講座用の問題らしい。 Union-Find木とは グループの併合と判定ができるアルゴリズム 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。 初期化 はじめに N 個のノードを用意する。はじめは、辺はない。 併合 片方の木の根からもう片方の木の根に接続する。 判定 それぞれのノードの根を辿り、同じノードだと同じグループ。違かったら別のグループ。 木のランク ここでは、木を構成する最大段数を意味する。 以下実装。 MAX_N = 100000 par = [0 for… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fb1u3.hateblo.jp%2Fentry%2F2019%2F11%2F08%2F030844" title="ATC 001 B Union Find - いろんなことで四苦Hack（仮）" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-11-08 03:08:44 rich https://b1u3.hateblo.jp/entry/2019/11/08/030844 1.0 100%