AtCoder Beginner Contest 292, E : Transitivity

問題文

　https://atcoder.jp/contests/abc292/tasks/abc292_e

問題概要

　単純有向グラフ $G = ( V, E )$ が与えられる．
　以下の操作を考える．

1. グラフ $\hat G = ( V, \hat E \leftarrow E )$ を用意する
2. 以下の操作を可能な限り適用する
   1. 相異なる頂点 $u, v, w$ であって，$( u, v ) \in \hat E$ かつ $( v, w ) \in \hat E$ かつ $( u, w ) \not \in \hat E$ なものを選ぶ
   2. 辺 $( u, w )$ を $\hat E$ に追加する

手順 2. が何回実行されるか求めよ．

制約

• $3 \leq |V| \leq 2{,}000$
• $0 \leq |E| \leq 2{,}000$

解法

　$\hat E$ にどのような辺が追加されるかを考えます．個人的にはそんなに自明ではないように感じますが Twitter では未証明に用いられがちな事実tとして，

• 2 頂点 $u, v$ について，$G$ において $u$ から $v$ へのパスがあれば，$( u, v ) \in \hat E$ である

というものがあります．示し方はいくつかあるかと思いますが，例えば数学的帰納法で示せます．

証明

　$\hat G$ における，始点 $u$ ，終点 $v$ のパスについて考える．パスの長さを $k$ とする．
　辺 $( u, v ) \in \hat E$ が存在することを数学的帰納法により示す．

• $k \leq 2$ のとき，$k = 1$ ならば自明，$k = 2$ ならば題意から成り立つ
• $k$ について成り立つとき，長さ $k + 1$ のパスを考える．このパスは長さ $k$ のパスと長さ $1$ のパス（＝辺）に分解できて題意から始点から終点に辺が張られるため成り立つ

　よって任意の $k < |V|$ について成り立つ．

続き

　以上のことから，$\hat E$ の説明は，

• $( u, v ) \in \hat E :=$ $G$ において $u$ から $v$ へのパスがある

と言い換えられます．この情報は $G$ の各頂点からの BFS や DFS を行えば計算できて，$\hat G$ との差分を数えれば答えが求まります．

計算量

　可達性を計算するための BFS or DFS が $|V|$ 回走るのに $O( |V| ( |V| + |E| ) )$ 時間かかります．その後の検証はそれより短い時間でできるので，全体で $O( |V| ( |V| + |E| ) )$ 時間となります．

コード

VI reachable( const VVI &G, const int s )
{
	const int N = SZ( G );

	VI reachability( N );

	queue< int > que;
	que.push( s );

	while ( !que.empty() )
	{
		const int u = que.front();
		que.pop();

		reachability[u] = 1;

		FOR( v, G[u] )
		{
			if ( !reachability[v])
			{
				que.push( v );
			}
		}
	}

	return reachability;
}

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N, M );
	VVI G( N ), Gm( N, VI( N ) );

	REP( M )
	{
		IN( int, u, v );
		--u, --v;
		G[u].PB( v );
		Gm[u][v] = 1;
	}

	VVI reachability;
	REP( i, N )
	{
		reachability.PB( reachable( G, i ) );
	}

	int res = 0;
	REP( u, N )
	{
		REP( v, N )
		{
			if ( u == v )
			{
				continue;
			}
			res += Gm[u][v] != reachability[u][v];
		}
	}


	cout << res << endl;

	return 0;
}