QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 2048 MB Puntuación total: 100

#7669. 迷宫化简

Estadísticas

Jay 经营着一家拥有各种游乐设施和景点的嘉年华。不幸的是,时运不济。最近发生的过山车事故、洗手间淹水以及一起不幸的小丑事件,让 Jay 的嘉年华在公众中声名狼藉。由于付费顾客减少,收入下降,他必须削减一些成本才能维持经营。

嘉年华最大的景点之一是一个巨大且令人困惑的迷宫。它由各种各样的圆形房间组成,房间之间由狭窄、蜿蜒的走廊连接。游客们喜欢在迷宫中迷路并试图绘制地图。Jay 注意到,其中一些房间可能实际上是完全相同的。如果是这样,他就能在不被任何人察觉的情况下缩小迷宫的规模。

如果当你被放入房间 $A$ 或 $B$(并且你知道迷宫的地图)时,仅通过探索迷宫无法分辨你最初是在 $A$ 还是 $B$,那么这两个房间 $A$ 和 $B$ 就是“实际上相同”的。

每个房间周围的走廊出口是均匀分布的,你不能在房间里做标记或留下任何东西(特别是,你无法判断你是否曾经访问过它)。房间唯一的识别特征是它们的出口数量。走廊也足够蜿蜒,以至于它们彼此之间无法区分,但当你进入一个房间时,你知道你是从哪条走廊进来的,因此你可以通过它们在房间周围出现的顺序进行简单的导航。

Jay 向嘉年华迷宫协会寻求帮助。那就是你!编写一个程序来确定迷宫中所有实际上相同的房间集合。

输入格式

输入包含单个测试用例。第一行包含一个整数 $n$,即迷宫中房间的数量($1 \le n \le 100$)。房间编号从 $1$ 到 $n$。接下来是 $n$ 行,按顺序描述每个房间。每行包含一个整数 $k$,表示该房间有 $k$ 条走廊($0 \le k < 100$),然后是 $k$ 个不同的整数,列出每条走廊连接的房间(按顺时针顺序,从任意起点开始)。房间不会连接到自身。

输出格式

为每个实际上相同的房间的极大集合(忽略大小为 $1$ 的集合)显示一行,其中包含集合中的房间编号,按升序排列。按集合中最小的房间编号对这些集合进行排序。如果没有这样的集合,则显示 none

样例

样例输入 1

13
2 2 4
3 1 3 5
2 2 4
3 1 3 6
2 2 6
2 4 5
2 8 9
2 7 9
2 7 8
2 11 13
2 10 12
2 11 13
2 10 12

样例输出 1

2 4
5 6
7 8 9 10 11 12 13

样例输入 2

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

样例输出 2

none

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.