e199: 資訊社的羈絆
Tags :
Accepted rate : 5人/6人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-05-24 10:28

Content

  資訊社一家親,為了加強歷屆所有資訊社社員的羈絆,我們希望能不斷加強人與人之間的關係。

  為此,你需要在已知的$\color{black}{\space N\space}$個人(編號$\color{black}{\space 1\sim N\space}$)之間不斷進行以下兩種操作:

  1. $\color{black}{\space add\;a\;b\space}$:加強編號$\color{black}{\space a\space}$和$\color{black}{\space b\space}$的關係,好讓資訊社的羈絆更穩固。

  2. $\color{black}{\space query\space}$:詢問有多少人$\color{black}{\space x\space}$滿足「存在一對$\color{black}{\space a,b\space}$,無論怎麼沿著人與人之間加強的關係走,都一定得經過$\color{black}{\space x\space}$才能從一方抵達另一方」。也就是當這個人消失,$\color{black}{\space a,b\space}$之間的間接強烈關係就會從原本存在變成斷開,這樣我們可能就得把$\color{black}{\space x\space}$列入觀察名單之中,為了方便起見,請你再由小到大把這些人的編號輸出出來。

  奮鬥吧!

Input

輸入首行有一個正整數$\color{black}{\space T(T\leq10)\space}$代表測資筆數。

每筆測資首行有兩個正整數$\color{black}{\space N,Q(N\leq600,Q\leq180300)\space}$,代表要加強關係的資訊社人數和操作次數,其中操作滿足$\color{black}{\space add\space}$操作不會重複加強同樣的兩個人的關係;$\color{black}{\space query\space}$操作不超過$\color{black}{\space 600\space}$次。

接下來$\color{black}{\space Q\space}$行,每行一種操作。

Output

對於每個$\color{black}{\space query\space}$操作,輸出一行,第一個數字$\color{black}{\space k\space}$代表滿足條件的人數,接下來由小到大輸出$\color{black}{\space k\space}$個數字代表滿足條件人們的編號。同一行的所有數字之間以空格隔開。

Sample Input
1
4 8
add 1 2
query
add 2 3
query
add 3 4
query
add 4 1
query
Sample Output
0
1 2
2 2 3
0
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (17%): 1.4s , <1M
不公開 測資點#1 (28%): 1.4s , <10M
不公開 測資點#2 (40%): 1.4s , <50M
不公開 測資點#3 (15%): 1.4s , <50M
Hint :

  範例測資中,第二筆$\color{black}{\space add\space}$操作後滿足$\color{black}{\space 2\space}$號消失後,$\color{black}{\space 1\space}$號和$\color{black}{\space 3\space}$號便從原本存在加強關係的連結轉為不存在,故第二次的$\color{black}{\space query\space}$將輸出$\color{black}{\space 1\;2\space}$,代表有$\color{black}{\space 1\space}$個人需要列入觀察名單,而這個人就是$\color{black}{\space 2\space}$號。

  第三筆$\color{black}{\space add\space}$操作後滿足$\color{black}{\space 2\space}$號或$\color{black}{\space 3\space}$號消失後,$\color{black}{\space 1\space}$號和$\color{black}{\space 4\space}$號便從原本存在加強關係的連結轉為不存在,故第三次的$\color{black}{\space query\space}$將輸出$\color{black}{\space 2\;2\;3\space}$,代表有$\color{black}{\space 2\space}$個人需要列入觀察名單,而這$\color{black}{\space 2\space}$個人就是$\color{black}{\space 2\space}$號和$\color{black}{\space 3\space}$號。

  第四筆無論讓誰消失,其餘的任兩個人都還是有辦法透過加強後的關係互通,因此沒有人需要列入觀察名單,故第三次的$\color{black}{\space query\space}$將輸出一個$\color{black}{\space 0\space}$。

 

  若使用了複雜度正確的演算法卻獲得TLE,請考慮壓常數。

 

  本題共有三組測試題組,條件限制如下所示。每一組可對應到一或多筆測試資料。

測資點$\color{black}{\space 0(17\%)\space}$:$\color{black}{\space N\leq 50\space}$,$\color{black}{\space query\space}$操作不超過$\color{black}{\space 10\space}$次。

測資點$\color{black}{\space 1(28\%)\space}$:所有$\color{black}{\space query\space}$操作都在$\color{black}{\space add\space}$操作之後,且$\color{black}{\space query\space}$操作只有一次。

測資點$\color{black}{\space 2\sim 3(55\%)\space}$:無特別限制。

Tags:
出處:
板橋高中校友盃 [管理者:
baluteshih (波路特石)
]


ID User Problem Subject Hit Post Date
18268
vincent97198 (學測戰士)
e199
弱弱的題解
51 2019-07-01 13:32