QOJ.ac

QOJ

Süre Sınırı: 2 s Bellek Sınırı: 2048 MB Toplam puan: 100

#7669. 迷宮縮減

İstatistikler

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.