QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#7669. 迷宮縮減

Statistics

Jay 經營著一座小型遊樂場,裡面有各種遊樂設施和景點。不幸的是,最近經營艱難。一場雲霄飛車事故、廁所淹水,以及一宗不幸的小丑事件,使 Jay 的遊樂場在大眾心中留下了壞名聲。付費遊客減少,收入下降,他必須削減一些成本才能繼續營業。

遊樂場最大的景點之一是一座巨大而令人迷惑的迷宮。它由各種圓形房間組成,房間之間以狹窄曲折的走廊相連。遊客喜歡在裡面迷路,並嘗試畫出地圖。Jay 注意到,有些房間可能實質上完全相同。若果真如此,他就能縮小迷宮,而不被任何人察覺。

若你被放入房間 $A$ 或 $B$ 之中(而且知道迷宮地圖),僅靠探索迷宮也無法判斷自己最初在 $A$ 還是 $B$,則稱兩個房間 $A$ 和 $B$ 實質上完全相同。走廊出口沿每個房間的周圍等距分布,你不能在房間裡做記號或留下任何東西(尤其無法判斷自己是否曾經來過)。房間唯一可辨認的特徵是出口數量。走廊也足夠曲折,彼此無法區分,但進入房間時,你知道自己從哪條走廊過來,因此可以利用走廊繞房間的排列順序稍作辨向。

Jay 向 Association for Carnival Mazery 求助。那就是你!請撰寫程式,找出迷宮中所有實質上完全相同的房間集合。

輸入格式

輸入只有一筆測試資料。第一行包含整數 $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.