编程题
### 问题描述 有 $n$ 个城市和 $m$ 个城市之间的航班连接。如果一个城市出现在从一个城市到另一个城市的所有航线上,则称为关键城市。 你的任务是找出从城市 $1$ 到城市 $n$ 的所有关键城市。 ### 输入格式 第一行有两个整数 $n$ 和 $m$,表示城市数量和航班数量。城市编号为 $1, 2, \dots, n$。 然后,有 $m$ 行描述连接。每行有两个整数 $a$ 和 $b$,表示从城市 $a$ 到城市 $b$ 有一条航线。所有航班都是单程的。 假设从城市 $1$ 到城市 $n$ 有一条航线。 ### 输出格式 首先输出一个整数 $k$,表示关键城市的数量。 第二行输出 $k$ 个整数:按升序排列的关键城市。 ### 样例输入 ``` 5 5 1 2 2 3 2 4 3 5 4 5 ``` ### 样例输出 ``` 3 1 2 5 ``` ### 评测数据规模 $1 \leq n \leq 10^5$,$1 \leq m \leq 2 \times 10^5$,$1 \leq a, b \leq n$。
查看答案
赣ICP备20007335号-2