QOJ.ac

QOJ

시간 제한: 1 s 메모리 제한: 32 MB 총점: 10

#13515. Bajtocka Agencja Informacyjna

통계

Bajtocka 信息局 (BAI) 拥有 $n$ 台计算机组成的网络。计算机的编号为 $1$ 到 $n$,其中 $1$ 号计算机是服务器。计算机之间通过单向信息通道连接。整个网络的结构保证可以从服务器直接或间接地向任何其他计算机发送信息。

当 BAI 获得新消息时,它会被放置在服务器上,然后在网络中传播。该机构的负责人想知道,如果其中一台计算机完全停止工作(例如由于恐怖袭击而被炸毁)会发生什么。在这种情况下,可能会出现新获得的信息无法到达其他某些计算机的情况,因为损坏的计算机是无法绕过的必经节点。如果某台计算机的故障会导致这种情况发生,我们称其为关键计算机。例如,在下图所示的情况下,关键计算机是编号为 $1$ 和 $2$ 的计算机——$1$ 是服务器,而从服务器发送到计算机 $3$ 的任何信息都必须经过计算机 $2$。

任务

编写一个程序,能够:

  • 从标准输入读取网络描述,
  • 找到所有关键计算机,
  • 将关键计算机的编号输出到标准输出。

输入格式

第一行包含两个整数 $n$ 和 $m$,由单个空格分隔。其中 $n$ 表示网络中的计算机数量($2 \le n \le 5\,000$),$m$ 表示信息通道的数量($n - 1 \le m \le 200\,000$)。

接下来的 $m$ 行中,每行描述一个信息通道,包含两个由单个空格分隔的整数 $a$ 和 $b$($1 \le a, b \le n$ 且 $a \ne b$),表示该通道将信息从编号为 $a$ 的计算机发送到编号为 $b$ 的计算机。你可以假设没有两个信息通道的起点和终点完全相同。

输出格式

输出应包含两行。

第一行应包含一个整数 $k$,表示关键计算机的数量。

第二行应包含所有关键计算机的编号,由单个空格分隔,并按升序排列。

样例

输入样例 1

4 5
1 2
1 4
2 3
3 4
4 2

输出样例 1

2
1 2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.