はまやんはまやんはまやん

hamayanhamayan's blog

Connect Cities [ACL Beginner Contest C]

https://atcoder.jp/contests/abl/tasks/abl_c

前提知識

解説

https://atcoder.jp/contests/abl/submissions/17050582

この問題設定をパッと見てUnionFindが真っ先に思い浮かんだので、途中考察がしにくいのだが、

  • 都市と道路を頂点と無向辺と捉えると、無向グラフとして考えられる
  • 「条件のどの都市からどの都市へも到達可能」が連結であるということに言い換えられる

みたいなところから思い浮かんでほしい。
既に存在する無向辺で連結成分に分けたとする。
全体を連結にするには、その連結成分をつないでやる必要があるが、ある2つの連結成分をつなぐのに必要な辺は1つで十分。
よって、連結成分数がgrp個であれば、それを1つにするにはgrp-1個の辺を追加すればいい。
無向グラフから連結成分数を抜き取るにはUnionFindを使うといい。
AtCoder LibraryではDSUとして実装されているので、それを使うとスムーズ。

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

    dsu uf(N);
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        uf.merge(a, b);
    }

    int ans = uf.groups().size() - 1;
    cout << ans << endl;
}