Dominator Tree

AC一覧

Problem Statement (Japanese) / 問題文 (日本語)

$N$ 頂点 $M$ 辺の有向グラフが与えられる。$i$ 番目の辺は頂点 $a_i$ から $b_i$ に貼られている。

頂点 $S$ を根とする dominator tree を求めよ。

Constraints / 制約

Input / 入力

$N$ $M$ $S$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$

Output / 出力

$p_0$ $p_1$ $p_2$ ... $p_{N - 1}$

$p_i$ は頂点 $i$ の親である。頂点 $S$ から頂点 $i$ へ到達できない場合、$-1$ を出力。また、$p_S = S$ とすること。

Sample / サンプル

# 1

5 6 0
0 1
1 2
2 3
3 4
0 3
2 4
0 0 1 0 0

# 2

8 8 4
4 2
4 3
2 0
3 0
0 1
3 5
3 6
7 6
4 0 4 4 4 3 3 -1

Forum


Timelimit: 5 secs