QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#6121. 包含头文件的黑客攻击

Statistics

短代码既酷又合理,既美观又优雅。你热爱短代码,因此你希望尽可能缩短代码长度。众所周知,有几种技巧可以缩短代码。今天,你将重点关注代码中的 includes(包含)。

你需要将 $N$ 个文件包含到你的代码中。这 $N$ 个文件编号为 $1$ 到 $N$。其中一些文件还会包含其他文件。如果文件 $a$ 包含文件 $b$,且文件 $b$ 包含文件 $c$,那么将 $a$ 包含到你的代码中就意味着将 $b$ 和 $c$ 也包含到你的代码中。但是,包含 $c$ 并不一定意味着包含 $a$ 或 $b$,除非 $c$(间接)包含 $a$ 或 $b$。

给定 $N$ 个文件的依赖关系信息,其中第 $i$ 条描述了文件 $a_i$ 包含文件 $b_i$。根据这些信息,你的任务是确定为了间接包含所有 $N$ 个文件,你必须直接包含的最少文件集合,并按升序输出该最小集合中的文件编号。如果这样的集合不唯一,则输出一个文件编号之和最小的集合。

输入格式

第一行包含两个整数 $N$ 和 $M$,其中 $N$ 是文件数量($1 \le N \le 30\,000$),$M$ 是依赖关系信息的数量($0 \le M \le 5 \times 10^5$)。接下来的 $M$ 行表示每条依赖关系,第 $i$ 行包含两个整数 $a_i$ 和 $b_i$,表示文件 $a_i$ 包含文件 $b_i$($1 \le a_i \le N, 1 \le b_i \le N$)。不存在重复的依赖关系信息,即对于 $1 \le i < j \le M$,不会同时满足 $a_i = a_j$ 和 $b_i = b_j$。

输出格式

确定为了间接包含所有文件,必须直接包含的最少文件数量,并按升序打印该文件集合中的文件编号。如果存在多个大小相同的集合,则输出一个文件编号之和最小的集合。

样例

样例输入 1

4 3
2 1
2 4
3 1

样例输出 1

2
3

样例输入 2

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

样例输出 2

3
5

样例输入 3

9 11
1 3
2 4
2 6
4 1
5 3
5 6
5 8
6 8
7 4
8 1
8 2

样例输出 3

5
7
9

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.