AtCoder Beginner Contest 350, D : New Friends

問題文

　https://atcoder.jp/contests/abc350/tasks/abc350_d

問題概要

　$1$ から $n$ で番号付けられた $n$ 人の人がいて，$m $ 組の友好関係がある．友好関係は $m $ 項からなる列 $A, B$ によって表され，$i$ 番目の友好関係は人 $A_i$ と人 $B_i$ が友人同士であることを示す．
　この人々に対し，次の操作を可能な限り行う．

1. 人 $x, y, z$ であって，人 $x, y$ 及び人 $y, z$ はそれぞれ友達同士であるが，人 $x, z$ は友達同士でないような三人を選ぶ．
2. 人 $x, z$ を友達同士にする．

　操作は何回行われるか？

制約

• $2 \leq n \leq 2 \times 10^5$
• $0 \leq m \leq 2 \times 10^5$
• $\forall ( i, j ), i \neq j \Rightarrow ( A_i, B_j ) \neq ( A_j, B_j )$

解法

　人を頂点，友好関係を辺とすれば自然に無向グラフ $G = ( V, E )$ を作ることができるので，以降はグラフの言葉を使っていきます．
　操作では条件を満たす $3$ 頂点 $u, v, w \in V$ を選ぶわけですが，どのような $3$ 頂点を選ぶことができるのか，もう少し考えます．まず明らかに不適なケースがあって，$u, w$ が異なる連結成分に属する場合は条件を満たしません．では $u, w$ が同じ連結成分に属するならば選べるのかというと，前準備として $0$ 回以上の操作をすることで YES となります．これはよく考えると（わたしにとっては？）自明ではないのですが，次のように示します．まず $u = P_1, P_2, \dots, P_l = w$ なるパス $P$ を用意します．$u, w$ が同じ連結成分に属する場合を考えているのでこれは可能です．$P$ の先頭 $k$ 要素の頂点から得られる誘導部分グラフ を $I_k = G[ \{ P_1, P_2, \dots, P_k \} ]$ と書くことにし，任意の $k \leq l$ について $I_k$ が完全グラフであることを示します．$k = 2$ のとき，$I_k$ は完全グラフです．$3 \leq k$ のときは次のようにします．

1. 可能な限り，以下の処理を繰り返す．
   1. $w = P_k$ とし，$u \in I_{ k - 1 }$ かつ $\{ u, w \} \not \in E$ な頂点 $u$ を選ぶ．
   2. $E \leftarrow E \cup \{ \{ u, w \} \}$ とする．
      • $P$ はパスであり，$I_{ k - 1 }$ が $2 \leq | I_{ k - 1 } |$ な完全グラフであることから，$v \neq u$ なる頂点 $v \in I_{ k - 1 }$ で $\{ v, w \} \in E$ なものが存在するので，これは可能．

上記処理の完了後，$I_k$ は完全グラフとなっています．従って $I_{ l - 1}$ も完全グラフにできるので，適当に $v \in I_{ l - 1 }$ を選ぶことで $u, w$ 間に辺を張ることができます．
　上述の証明から察せますが，パスの端点は連結成分内から任意に選べるので，操作完了後，各連結成分はクリークになります．頂点数が $n'$ な完全グラフの頂点数は二項係数 $\binom n 2 = \frac{ n' ( n' - 1 ) } 2$ と計算できるので，操作回数としてはそこから連結成分に属する辺の数を引いた値となります．
　ということで，各連結成分についてそのサイズと関係する辺の数が分かれば問題を解くことができます．実装方法はいくつかある気がしますが，持っていれば（あるいは ACL を使えば）素集合データ構造（いわゆる Union-Find）を使うと楽な気がします．この場合，計算量はいわゆる Ackermann 関数の逆関数を $\alpha( n )$ として均し $O( n + m \alpha( n ) )$ 時間となります．

コード

class DisjointSetForest;
// 中身省略
// DisjointSetForest( N )
// find( x )
// same( x, y )
// unite( x, y )
// groups()
// groupSize( x )

int main()
{
	IN( int, N, M );
	VPII es( M );
	FOR( e, es )
	{
		cin >> e.fst >> e.snd;
		--e.fst, --e.snd;
	}

	DisjointSetForest dsf( N );
	FOR( e, es )
	{
		dsf.unite( e.fst, e.snd );
	}

	VI numedges( N ), sizes( N );
	FOR( e, es )
	{
		++numedges[ dsf.find( e.fst ) ];
		sizes[ dsf.find( e.fst ) ] = dsf.groupSize( dsf.find( e.fst ) );
	}

	LL res = 0;
	REP( i, N )
	{
		const LL s = sizes[i];
		res += s * ( s - 1 ) / 2 - numedges[i];
	}

	cout << res << endl;

	return 0;
}