f292: 11987 - Almost Union-Find
Tags : DSU
Accepted rate : 6人/15人 ( 40% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-19 23:04

Content

大家應該都聽過查並集這個資料節構吧?需要提供兩個功能 Find() 和 Union(),

現在我們需要再額外増加一個新功能:把某個數字從他現在的群體中移除並加入指定的群體當中。

當然一開始時每個數字都是屬於自己的群體 {1}, {2}, {3}, ..., {n}。

操作的定義:

1  P  Q:將 P Q 所在的兩個群體合併為同一個

2  P  Q:將 P 從他所在的群體當中移除並且加入 Q 所在的群體

3 P      :印出 P 所在的群體包含的成員個數和成員編號總合

 

 
Input

多筆測資輸入,最後以 EOF 結尾。

每筆測資的第一行輸入 2 個整數 N 和 M ,N 代表數字的編號從 1 到 N , M 代表 操作的次數。

接著每一行都是屬於題目定義的操作方式三種其中一種。

測資範圍保證 1 ≦ N, M ≦ 100,000 且 1 ≦ P, Q ≦ N。

Output

每一行輸出 2 個數字代表對應的第 3 種操作執行結果。

Sample Input #1
5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3
Sample Output #1
3 12
3 7
2 8
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <10M
公開 測資點#1 (50%): 1.0s , <1M
Hint :

Disjoint Set Union

Tags:
DSU
出處:
UVA 11987 [管理者:
rollfc (胖胖貓)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」