QOJ.ac

QOJ

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

#11882. 锦标赛

الإحصائيات

国际 X-Game 联合会组织了一场比赛,参赛者为若干个程序。编号从 $1$ 到 $n$ 的程序参加了此次比赛。比赛规则如下:只要比赛中剩余的程序多于一个,就会随机选择两个(不同的)程序进行比赛。失败者(X-Game 中没有平局)将被淘汰,整个过程重复进行。在进行了全部 $n-1$ 场比赛后,唯一留在比赛中的程序即为获胜者。

联合会拥有以往比赛的结果表。已知这些程序以确定性的方式(即以可重复的方式)进行比赛,且表现与以往比赛完全相同。因此,如果两个程序之前已经交手过,那么它们的下一次比赛结果将与之前相同。然而,如果它们从未交手过,则比赛结果无法预测——双方都有获胜的可能。联合会希望得到所有有希望赢得比赛的程序列表。

请编写一个程序,完成以下任务:

  • 从标准输入读取参赛程序的数量以及以往比赛的结果表;
  • 确定所有有希望赢得比赛的程序;
  • 将结果写入标准输出。

输入格式

第一行包含一个整数 $n$,$1 \le n \le 100\,000$。接下来的 $n$ 行包含以往比赛的结果表:第 $(i+1)$ 行包含一个整数 $k_i$($0 \le k_i \le n$),随后是 $k_i$ 个不等于 $i$ 的程序编号(按升序排列),这些是程序 $i$ 此前曾战胜过的程序编号。行内的数字由单个空格分隔。所有已知的以往比赛结果总数不超过 $1\,000\,000$。

输出格式

标准输出的第一行也是唯一一行应包含有希望赢得比赛的程序数量 $w$,随后是这 $w$ 个程序的编号,按升序排列。数字之间应由单个空格分隔。

样例

输入 1

4
2 2 3
0
1 2
1 2

输出 1

3 1 3 4

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.