torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 245, F : Endless Walk

問題概要

 単純有向グラフ $G = ( V, E )$ が与えられる.
 頂点 $v \in V$ であって,$v$ を始点として $G$ 上で無限に(辺に沿った)移動を繰り返すことができるものの個数を求めよ.

制約

  • $1 \leq |V| \leq 2 \times 10^5$
  • $0 \leq |E| \leq \min( |V| ( |V| - 1 ), 2 \times 10^5 )$

解法

 まず,頂点 $v \in V$ が問題文の条件を満たす場合とはどういうことか,ちょっと考えてみます.無限回移動を繰り返すことができるということは,(鳩ノ巣原理を持ち出すまでもなく,)同じ頂点を何度も訪問していることになります.つまり,どこかの閉路をぐるぐる回り続けることで無限回の移動を達成することになります.従って,$v$ の条件としては,$v$ から $G$ のいずれかの閉路(に含まれる頂点)に到達することができるような $v$ が数えるべき頂点です.
 ということで,$G$ の閉路を検出したい気持ちになってきます.その方法としては,DFS をするなどしてもよいですし,持っていれば(あるいはすぐに書けるなら)強連結成分分解を利用することができます.$G$ を強連結成分分解したとき,閉路はサイズが $2$ 以上の強連結成分として現れます.
 各頂点 $v \in V$ から特定の頂点群への可達性を判定したいわけですが,各頂点を始点とした探索を毎回やったりすると TLE します*1.なのでちょっと工夫します.しばしば使うテクなので覚えて帰って欲しいのですが,こういう場合は,$G$ の辺の向きを全て逆にしたグラフ $G_r = ( V, \{ ( v, u ) \mid ( u, v ) \in E \} )$ を考えます.頂点 $u \in V$ から $G_r$ 上で頂点 $v \in V$ に到達できるとき,$G$ 上で $v$ から $u$ に到達できます.よって,$G_r$ 上で一回 BFS をすれば,任意の頂点 $v \in V$ からの $G$ 上での $u$ への可達性を求められます.このことを利用して,属する連結成分のサイズが $2$ 以上となる全ての頂点を始点とした(=最初にキューに突っ込んだ)BFS を $G_r$ 上で行うことで,$G$ 上で閉路に到達できる頂点たちを列挙できます.
 この解法は,$G$ に対する強連結成分分解を一回行い,$G_r$ 上での BFS を一回行います.強連結成分分解は 2 回の DFS で実装できるので,これらの操作はどちらも $O( |V| + |E| )$ 時間で動作します.入出力などのその他の操作もこのオーダーを超えないので,全体としても $O( |V| + |E| )$ 時間となります.

コード

// 強連結成分分解 / Strongly Connected Component
// O( |V| + |E| )
class StronglyConnectedComponents
// connect( from, to )
// solve() : 連結成分の数が返る
// componentNumbers() : 頂点番号→連結成分の番号 の表が返る
// 連結成分の番号の大小は、トポロジカル順序の大小と一致

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

	IN( int, N, M );
	VVI G_r( N );
	StronglyConnectedComponents scc( N );

	REP( M )
	{
		IN( int, u, v );
		--u, --v;
		G_r[v].PB( u );
		scc.connect( u, v );
	}

	const int K = scc.solve();
	const VI belongs = scc.componentNumbers();
	VI sizes( K );
	REP( i, N )
	{
		++sizes[ belongs[i] ];
	}

	queue< int > que;
	REP( i, N )
	{
		if ( 2 <= sizes[ belongs[i] ] )
		{
			que.push( i );
		}
	}

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

		feasible[u] = true;

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

	cout << accumulate( ALL( feasible ), 0 ) << endl;

	return 0;
}

*1:例えば DFS や BFS は一回あたり $O( |V| + |E| )$ 時間で,これを $|V|$ 回行うと $O( |V| ( |V| + |E| ) )$ になって死にます.