ACL Beginner Contest, C : Connect Cities

問題文

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

問題概要

　$N$ 個の街と $M $ 本の道路がある．$i$ 番目の道路は街 $A_i$ と $B_i$ を双方向に繋いでいる．
　ここに，新たに（双方向の）道路を作る操作を任意の回数行うことができる．任意の街から任意の街へ到達可能にするために必要な操作の回数の最小値はいくらか？

制約

• $2 \leq N \leq 100{,}000$
• $1 \leq M \leq 100{,}000$
• その他 $A, B$ に関するいい感じの制約

解法

　街を頂点・道路を辺としたグラフ $G = ( V, E )$ を考えます．$G$ の連結成分を一つの頂点に潰して新たな頂点集合 $\hat V$ を作ると，新たなグラフ $\hat G = ( \hat V, \emptyset )$ が得られます．$\hat G$ を連結にできれば，$\hat V$ の対応する連結成分間で適当に辺を張る操作で $G$ も連結にできます．
　連結で辺陬最小のグラフというのは木になるので $\hat G$ を木にすればよく，木の辺数は頂点数 - 1 なので，（辺が無い状態から始めることから） $| \hat V | - 1$ が答えです．この値は，素集合データ構造（いわゆる Union-Find で連結成分を求めて，連結成分の個数を数えれば求めることができます．

コード

class DisjointSetForest;
// DisjointSetForest( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )

int main()
{
	IN( int, N, M );
	VI A( M ), B( M );
	REP( i, M )
	{
		cin >> A[i] >> B[i];
		--A[i], --B[i];
	}

	DisjointSetForest dsf( N );
	REP( i, M )
	{
		dsf.unite( A[i], B[i] );
	}

	cout << dsf.groups() - 1 << endl;

	return 0;
}