torus711 のアレ

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

AtCoder Beginner Contest 168, D : .. (Double Dots)

問題概要

 $N$ 頂点 $M $ 辺の連結な重み無し単純無向グラフが与えられる.各頂点に以下の条件を満たす「道標」を設定せよ.

  • 道標は隣接する頂点を指す
  • 道標が指す頂点への移動を繰り返すとき,頂点 $1$ へ最小の移動回数で辿り着ける

 なお,解が存在しない場合はそのことを報告せよ.

制約

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • (その他 $A, B$ に関するいい感じの制約)

解法

 グラフが連結であることから,各頂点 $u$ から頂点 $1$ への最短経路は必ず存在します.その最短経路長を $d_u$ と書くことにします(なお,$d_1 = 0$ です).更に言えば,頂点 $1$ を除く各頂点 $u$ について,$d_v = d_u - 1$ を満たす頂点が少なくとも 1 つ隣接しています.このことは,

  • 距離(移動回数)は $1$ ずつ増えるので,経路が存在するならばちょうど $1$ 少ない頂点が隣接しているはず

ということから言えます.また,$d_v$ は $u$ に隣接する頂点たちの $d$ の内で最小の値をとります*1.なぜなら,

  • 更に小さい値をもつ頂点 $w$ があるとすれば,$d_w + 1 < d_u$ となってしまい,$d$ が最短経路長であることに反する

からです.2 つをまとめれば,「頂点 $1$ に最も近い頂点に移動するのは,最短経路の辿り方の 1 つである」と言えます(経路の辿り方であって,頂点 $1$ に最も近いところに移動しているので).よって,そのような辺(の行き先)を道標とすることによって,制約を満たす任意の入力に対して解を構成できます.
 具体的な構成方法としては幅優先探索 (Breadth FIrst Search) を用います.ただし,今回は最短経路長自体は必要無く,どこから来たかだけが重要なので,各頂点について「未訪問を示すマークか,訪問元を表す番号」を記録した配列を作って更新していくだけでよいです.
 計算量としては BFS を一回行い,BFS は各頂点と各辺をそれぞれ定数回ずつ参照するので,$O( N + M )$ になります.

コード

int main()
{
	IN( int, N, M );
	VVI G( N );
	REP( M )
	{
		IN( int, u, v );
		--u, --v;
		G[u].PB( v );
		G[v].PB( u );
	}

	VI parents( N, -1 );
	parents[0] = 0;
	queue< int > que;
	que.push( 0 );

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

		FOR( v, G[u] )
		{
			if ( parents[v] == -1 )
			{
				parents[v] = u;
				que.push( v );
			}
		}
	}

	cout << "Yes" << endl;
	transform( begin( parents ) + 1, end( parents ),
			OSI< int >( cout, "\n" ),
			bind( plus< int >(), _1, 1 ) );
	cout << flush;

	return 0;
}

*1:unique とは限らない