← 返回题目列表

AtCoder · icpc2014summer_day4_i

I. 资本

中文机器翻译题面 查看原题

问题陈述

给出了一个无环的连通有向图。 (有向图如果是无向图则连通。)

我想为此图选择一个顶点并确定大写$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