QOJ.ac

QOJ

حد الوقت: 3 s حد الذاكرة: 512 MB مجموع النقاط: 100

#335. 多向街道

الإحصائيات

Byteasar 正在考虑搬到 Bytown 并租一套公寓。Bytown 是一座美丽的城市,拥有许多优点,但对于司机来说却是一场噩梦。城中有 $n$ 个交叉路口,由 $m$ 条街道组成的网络连接,这些街道的分布或多或少有些杂乱。街道非常狭窄,必须单向通行。令人惊讶的是,城市规划者最近想出了一种变通方法,可以在不拓宽街道的情况下实现双向通行。具体来说,他们意识到交通不需要同时双向流动。因此,在奇数日,交通按照自古以来的方式流动,而在偶数日,所有街道的方向都会反转。

Byteasar 想在一个交通便利的地方租一套公寓。具体来说,他想找一个交叉路口,使得从该路口出发,可以在一天之内到达其他所有交叉路口——对于某些目的地,这可能是奇数日,而对于另一些目的地,则可能是偶数日。回程可以忽略不计,因为在最坏的情况下,Byteasar 可以在第二天原路返回。

给定 Bytown 的道路网络,确定所有满足 Byteasar 要求的交叉路口。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($n \ge 2, m \ge 1$),由单个空格分隔,分别表示 Bytown 的交叉路口数量和街道数量。交叉路口编号为 $1$ 到 $n$。接下来的 $m$ 行描述了街道:第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$),由单个空格分隔,表示有一条从交叉路口 $a_i$ 指向交叉路口 $b_i$ 的单向街道(即在奇数日,街道可以从 $a_i$ 遍历到 $b_i$,而在偶数日,街道可以从 $b_i$ 遍历到 $a_i$)。每个有序对 $(a_i, b_i)$ 在输入中最多出现一次。

输出格式

第一行输出一个整数 $k$,表示满足 Byteasar 要求的交叉路口数量。第二行输出一个递增的序列(长度为 $k$),包含这些交叉路口的编号,并用空格分隔。如果 $k = 0$,则第二行应为空;你的程序可以输出一个空行,也可以不输出。

样例

样例输入 1

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

样例输出 1

4
1 4 5 6

说明

样例说明:从交叉路口 $1$ 出发,可以在奇数日到达所有其他交叉路口。从交叉路口 $5$ 和 $6$ 出发,可以在偶数日到达所有其他交叉路口。从交叉路口 $4$ 出发,可以在奇数日到达交叉路口 $5$ 和 $6$,而在偶数日到达交叉路口 $1, 2$ 和 $3$。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试组。

子任务 数据范围 分值
1 $n, m \le 5000$ 28
2 $n \le 300\,000, m \le 1\,000\,000$;对于每个满足要求的交叉路口,所有其他交叉路口均可在奇数日到达 29
3 $n \le 500\,000, m \le 1\,000\,000$ 43

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.