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; }