問題概要
$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 とは限らない