2003 . 樹狀圖

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

tmwilliamlin
我的中文很爛

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

11.9% (7/59)

Tags

union-find

Description

上了魔法大學正在修普生的小向，寫了一個畫出物種關係樹狀圖的程式。程式執行的結果大概就像下面這樣：

每一條橫線都代表他們所連接的豎線所連接到的物種們有關係。愈低的橫線代表關係愈近，而愈高的橫線則代表關係愈遠。

然而小向太久沒寫code了，所以寫出來的程式有兩個問題：第一個就是這個樹狀圖不一定是連通的，不過其實這沒有什麼關係；第二個問題是這個樹狀圖可能長得亂亂的，如下圖：

這種有相交的樹狀圖長得實在不是很討喜。不過小向發現只要適當地變換底下物種的順序，就可以幫亂亂的樹狀圖變成跟第一張圖一樣乾淨的樹狀圖。

小向想破了頭還是想不出要怎麼把這個bug給修好，所以他只好把這個題目放在TIOJ了。

Input Format

第一行有兩個整數0<N≤106,0≤M<N, 分別代表物種的個數以及橫線的個數。
接下來的M行中每一行都會有一條橫線以及他所連接的豎線的訊息。具體來說，每一行都會有整數0≤Y≤109,2≤L≤N,1≤V1,V2,…,VL≤N, 分別代表橫線的y軸值，橫線所連接的豎線個數，以及每條豎線連接的物種團中的某一個物種。

保證所給的測資可以畫出合法的樹狀圖。也就是說對於每個物種，他所會連到的橫線的高度都相異，而且每一條橫線和物種團之間最多只會有一條豎線。但不保證給定的樹狀圖是連通的。

Output Format

輸出一行，包含N個用空格隔開的數，代表其中一種乾淨的樹狀圖的排法。若有很多種，請輸出字典序最小的答案。

Sample Input 1

6 4
10 3 2 4 5
40 2 1 5
20 2 1 3 
30 2 3 6

Sample Output 1

1 3 6 2 4 5

Hints

本題的輸入輸出量非常大，建議C++輸入輸出使用者加入std::cin.tie(0);以及ios_base::sync_with_stdio(0)兩行，同時不要使用C式輸出。

Problem Source

Problem Set / Description by Paupière
題目取自MIT ACM ICPC校內團體賽第四題強化版

Subtasks

No. Testdata Range Constraints Score
1 0~4 N≤10 8
2 0~9 N≤104 12
3 0~14 N≤105 30
4 0~19 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1 2 3 4
1 1000 131072 262144 1 2 3 4
2 1000 131072 262144 1 2 3 4
3 1000 131072 262144 1 2 3 4
4 1000 131072 262144 1 2 3 4
5 1000 131072 262144 2 3 4
6 1000 131072 262144 2 3 4
7 1000 131072 262144 2 3 4
8 1000 131072 262144 2 3 4
9 1000 131072 262144 2 3 4
10 1000 131072 262144 3 4
11 1000 131072 262144 3 4
12 1000 131072 262144 3 4
13 1000 131072 262144 3 4
14 1000 131072 262144 3 4
15 1000 131072 262144 4
16 1000 131072 262144 4
17 1000 131072 262144 4
18 1000 131072 262144 4
19 1000 131072 262144 4
Submit
Back to Top