#G1199. [GESP202609 七级] 必经之路

[GESP202609 七级] 必经之路

[GESP202609 七级] 必经之路

时间限制:1.0 s 内存限制:512.0 MB

题目描述

给定一张有 nn 个结点、mm 条边的有向图 GG,GG 中的结点依次以 1,2,…,n1, 2, \ldots, n 编号。第 ii 条边(1≤i≤m1 \le i \le m)从结点 uiu_i 指向结点 viv_i。

GG 中任一入度为 0 的结点可以作为合法起点,任一出度为 0 的结点可以作为合法终点。

如果 GG 中所有可能的从合法起点到合法终点的路径都会经过结点 vv,则称 vv 是必经点。注意必经点可以为合法起点或合法终点。

请你求出 GG 中所有必经点的编号。

例如,在下图中合法起点有点 1 与点 2,合法终点有点 7 与点 8。

所有合法起点到合法终点的路径为:

  • 1→3→4→5→6→71 \to 3 \to 4 \to 5 \to 6 \to 7
  • 1→3→4→5→6→81 \to 3 \to 4 \to 5 \to 6 \to 8
  • 1→3→4→5→71 \to 3 \to 4 \to 5 \to 7
  • 2→3→4→5→6→72 \to 3 \to 4 \to 5 \to 6 \to 7
  • 2→3→4→5→6→82 \to 3 \to 4 \to 5 \to 6 \to 8
  • 2→4→5→6→72 \to 4 \to 5 \to 6 \to 7
  • 2→4→5→6→82 \to 4 \to 5 \to 6 \to 8
  • 2→4→5→72 \to 4 \to 5 \to 7

因此必经点有两个,编号分别为 4 与 5。

输入格式

第一行,两个正整数 n,mn, m,表示有向图 GG 中的结点数与边数。

接下来 mm 行,每行两个正整数 ui,viu_i, v_i,表示一条从结点 uiu_i 指向结点 viv_i 的有向边。

保证 GG 中至少有一个合法起点,至少有一个合法终点,且至少存在一条从一个合法起点到一个合法终点的路径,同时不存在孤立点(即出度和入度都为 0 的点)。

输出格式

第一行,一个整数,表示必经点的数量 kk。

如果存在必经点,则第二行从小到大输出 GG 中所有必经点的编号。

样例 #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 1≤n≤1001 \le n \le 100,1≤m≤2001 \le m \le 200 无
全部 1≤n≤10001 \le n \le 1000,1≤m≤20001 \le m \le 2000 保证 GG 中至少有一个合法起点,至少有一个合法终点,且至少存在一条从一个合法起点到一个合法终点的路径,同时不存在孤立点