Dominator Tree

AC一覧

Problem Statement
問題文

Given a directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$.

Calculate the dominator tree of this graph whose root is $S$.

$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$ is the parent of vertex $i$. If we can not reach $i$ from $S$, print $-1$. $p_S$ is $S$.

$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

Before submitting, please confirm terms and conditions