[AtCoder] ACL Beginner Contest C – Connect Cities

問題

方針

Union-Find

グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups() のサイズを利用してもいいですが、ライブラリにグループ数を定義し、グループが統合されるたびにグループ数を減らしていけばいいです。

幅優先探索

連結されているグラフを一つの集合とみて、その集合の数を求めれば良いので幅優先探索でグループ数を求めます。隣接リストを作成し、キューを使って幅優先探索を行います。

コード

Union-Find

幅優先探索