a203. 4. 真假子圖 - 彰化精誠中學

內容

情報調查局內有 n個工作人員, 調查局負責人將這些人秘密分成兩組 A和 B並不讓其他人知道, 並將合作名單分配給組長, 合作名單是由很多個 pair組成, 每個 pair (x,y) 代表 x 和 y 需要合作完成任務, 並且保證 x和 y不會同時在 A組或是同時在 B組

組長不小心將這個合作名單分配遺失, 僅剩下其中 m個 pair, 為了要復原這些失去的資料, 組長派出了另外 p個調查員編號 1 到 p去調查這個合作關係, 每一個調查員都會回傳恰好 k個 pair的資料回來

有些調查員回傳的資料和組長手上的資料會產生矛盾 (意即加上這 k個 pair 和組長手上存留的 m個 pair會使得這些人是被分成 A, B兩組這件事產生矛盾), 請將回傳錯誤結果的調查員編號由小到大輸出出來, 保證至少一個且最多三個。

另外保證若調查員的 k個 pair的結果和組長存留的 m個 pair不會產生矛盾, 則保證調查員的資料一定和原本 A, B分組吻合

輸入說明

第一行先輸出兩個正整數 n和 m

第二行來有 2m個非負整數兩兩形成一個數對，表示目前還留存的 m個 pair

第三行有兩個正整數 p和k

並且接下來的 p行每行有 2k個非負整數, 兩兩形成一對代表某個調查員找到的 k個pair

數字範圍

1≤n,m≤20000
2≤p≤10000,1≤k≤20
每一個人被 pair 提到的次數 ≤150

子題配分

(20%): 1≤n,m≤100,1≤p≤20,ans=1
(20%): 1≤n,m≤5000,1≤p≤200
(60%): 無額外限制

輸出說明

由小到大輸出會形成矛盾的調查員編號，每個編號各自獨立一行

範例輸入 #1

7 5
0 1 0 2 1 3 2 3 4 5
2 3
0 6 2 4 3 6
0 6 0 3 3 5

範例輸出 #1

範例輸入 #2

範例輸出 #2

1
3

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1M
公開測資點#4 (5%): 0.5s , <1M
公開測資點#5 (5%): 0.5s , <1M
公開測資點#6 (5%): 0.5s , <1M
公開測資點#7 (5%): 0.5s , <1M
公開測資點#8 (5%): 0.5s , <1M
公開測資點#9 (5%): 0.5s , <10M
公開測資點#10 (5%): 0.5s , <10M
公開測資點#11 (5%): 0.5s , <1M
公開測資點#12 (5%): 0.5s , <1M
公開測資點#13 (5%): 0.5s , <1M
公開測資點#14 (5%): 0.5s , <1M
公開測資點#15 (5%): 0.5s , <1M
公開測資點#16 (5%): 0.5s , <10M
公開測資點#17 (5%): 0.5s , <10M
公開測資點#18 (5%): 0.5s , <1M
公開測資點#19 (5%): 0.5s , <10M

提示：

標籤:

並查集二分圖判斷二分搜尋圖論群試演算法

出處:

2021年11月APCS cthbst (吳宗達) [管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」