仁義なきサルたち [yukicoder No.556]

https://yukicoder.me/problems/no/556

解説放送

未定

前提知識

UnionFind

解説

https://yukicoder.me/submissions/196779

戦いをシミュレートする。
ここでUnionFindというデータ構造を使う。参考
UnionFindで併合するときにグループ内の要素数も合わせておく。
あとは、このUnionFindを使ってどっちが勝つかを確かめていく。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    UnionFind uf(N);

    rep(i, 0, M) {
        int A, B; cin >> A >> B; A--; B--;
        if (uf[A] != uf[B]) {
            int a = uf[A], b = uf[B];

            if (uf.cnt[a] < uf.cnt[b]) uf(a, b);
            else if (uf.cnt[a] > uf.cnt[b]) uf(b, a);
            else {
                if(uf[a] < uf[b]) uf(b, a);
                else  uf(a, b);
            }
        }
    }

    rep(i, 0, N) printf("%d\n", uf[i] + 1);
}