#G1199. [GESP202609 七级] 必经之路
[GESP202609 七级] 必经之路
[GESP202609 七级] 必经之路
时间限制:1.0 s 内存限制:512.0 MB
题目描述
给定一张有 个结点、 条边的有向图 , 中的结点依次以 编号。第 条边()从结点 指向结点 。
中任一入度为 0 的结点可以作为合法起点,任一出度为 0 的结点可以作为合法终点。
如果 中所有可能的从合法起点到合法终点的路径都会经过结点 ,则称 是必经点。注意必经点可以为合法起点或合法终点。
请你求出 中所有必经点的编号。
例如,在下图中合法起点有点 1 与点 2,合法终点有点 7 与点 8。
所有合法起点到合法终点的路径为:
因此必经点有两个,编号分别为 4 与 5。
输入格式
第一行,两个正整数 ,表示有向图 中的结点数与边数。
接下来 行,每行两个正整数 ,表示一条从结点 指向结点 的有向边。
保证 中至少有一个合法起点,至少有一个合法终点,且至少存在一条从一个合法起点到一个合法终点的路径,同时不存在孤立点(即出度和入度都为 0 的点)。
输出格式
第一行,一个整数,表示必经点的数量 。
如果存在必经点,则第二行从小到大输出 中所有必经点的编号。
样例 #1
样例输入 #1
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 4
5 7
样例输出 #1
2
4 5
样例 #2
样例输入 #2
8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 5
4 7
样例输出 #2
0
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| 1~4 | , | 无 |
| 全部 | , | 保证 中至少有一个合法起点,至少有一个合法终点,且至少存在一条从一个合法起点到一个合法终点的路径,同时不存在孤立点 |