AT_abc315_e [ABC315E] Prerequisites

题目描述

有 $N$ 本编号为 $1$ 到 $N$ 的书。
第 $i$ 本书有 $C_i$ 本前置书籍，其中第 $j$ 本为 $P_{i,j}$，在阅读第 $i$ 本书之前，必须先读完这 $C_i$ 本前置书籍。
保证可以通过适当的顺序读完所有书。

你想以最少的阅读量来阅读第 $1$ 本书。
请按应当阅读的顺序输出除第 $1$ 本书以外，必须要读的书的编号。满足条件的阅读顺序可能有多种，只需输出其中一种即可。
在这些条件下，需要阅读的书的集合是唯一确定的。

输入格式

输入以如下格式从标准输入给出。

$N$ $C_1$ $P_{1,1}$ $\ldots$ $P_{1,C_1}$ $C_2$ $P_{2,1}$ $\ldots$ $P_{2,C_2}$ $\vdots$ $C_N$ $P_{N,1}$ $\ldots$ $P_{N,C_N}$

输出格式

输出为阅读第 $1$ 本书所需的最少数量的书时，这些书的编号，按应当阅读的顺序，用空格分隔。

输入输出样例 #1

输入 #1

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

输出 #1

5 3 4 2

输入输出样例 #2

输入 #2

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

输出 #2

6 5 4 3 2

输入输出样例 #3

输入 #3

8
1 5
1 6
1 7
1 8
0
0
0
0

输出 #3

5

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq C_i < N$
• $\sum_{i=1}^{N} C_i \leq 2 \times 10^5$
• $C_1 \geq 1$
• $1 \leq P_{i,j} \leq N$
• 当 $1 \leq j < k \leq C_i$ 时，$P_{i,j} \neq P_{i,k}$
• 保证可以读完所有书

样例说明 1

为了阅读第 $1$ 本书，需要先读第 $2,3,4$ 本书；为了读第 $2$ 本书，需要先读第 $3,5$ 本书；为了读第 $4$ 本书，需要先读第 $5$ 本书。第 $3,5,6$ 本书不需要再读其他书。此时，例如按 $5,3,4,2$ 的顺序阅读，可以读到第 $1$ 本书。在读完 $3$ 本或更少的书时无法读到第 $1$ 本书，因此这是一个答案。也可以按 $3,5,4,2$ 的顺序等，只要在读完 $4$ 本书后能读到第 $1$ 本书即可。

由 ChatGPT 4.1 翻译