问题陈述
给出了一个无环的连通有向图。 (有向图如果是无向图则连通。)
我想为此图选择一个顶点并确定大写$s$。
$T(v)$ = “使所有点均可从 $v$ 到达所需的‘翻转边缘’操作的最小数量。”
然而,“边反转”意味着删除相对于顶点 $v,u$ 附加到 $(v,u)$ 的有向边,并将其重做到 $(u,v)$。
如果 $T(s)\leq T(v)$ 对于任何顶点 $v$ 成立,则顶点 $s$ 是大写字母。
列出所有大写顶点。
输入
输入按以下格式在 $M+1$ 行中给出。
$N$ $M$
$a_1$ $b_1$
:
:
$a_M$ $b_M$
- 第一行给出了两个整数$N$和$M$,表示给定的图有$N$个顶点和$M$个边。
- 第2行到$M+1$中分别给出了两个整数$a_i和b_i$,表示有向边从$a_i$拉伸到$b_i$。
约束
- $1 \leq N \leq 10{,}000$
- $0 \leq M \leq 100{,}000$
- $0 \leq a_i \leq N-1 $
- $0 \leq b_i \leq N-1 $
- $a_i \neq b_i$
- $i \neq j $ 然后 $(a_i, b_i) \neq (a_j, b_j)$
- 给定的图是连通的并且没有循环。
- 对于给定的图,度数为 0 的顶点数小于或等于 50。
输出
按以下格式分两行输出。
$cnum$ $cost$
$c_1$ $c_2$ ... $c_{cnum}$
- 在第一行,输出两个整数 $cnum$ 和 $cost$,以空格分隔。
- 在第二行,输出 $cnum$ 个整数 $c_i$,以空格分隔。
- 变量含义如下。
- $cnum$ :满足资本属性的顶点数
- $cost$ :大写顶点 $v$ 的 $T(v)$ 值
- $c_i$ :满足 Capital 属性的顶点按数量升序排列时的第 $i$ 个顶点数
示例输入 1
3 2 0 1 2 1
样本输入 1 的输出
2 1 0 2
- 当顶点 0 为首都时,通过反转边 (2,1),将创建边为 (0,1) 和 (1,2) 的图,因此 1 就是答案。
- $T(0)=1$,$T(1)=2$,$T(2)=1$。
示例输入 2
5 4 0 1 2 1 2 3 4 3
样本输入 2 的输出
3 2 0 2 4
示例输入 3
5 5 0 1 1 2 3 2 3 4 4 1
样本输入 3 的输出
2 1 0 3