g598. 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$

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

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

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

數字範圍

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

子題配分

(20%): $1 \leq n, m \leq 100, 1 \leq p \leq 20, a n s = 1$
(20%): $1 \leq n, m \leq 5000, 1 \leq p \leq 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

測資資訊：

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

提示：

標籤:

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

出處:

2021年11月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
41482	sophie198205 ... (闕河正)	g598	不使用DFS與二分搜，單純用並查集做法	272	2024-07-30 22:13
43516	r1cky (hehe)	g598	不用二分搜和DSU的作法	115	2024-10-21 12:51
41789	toseanlin@gm ... (Dr. SeanXD)	g598	C++詳解－並查集	197	2024-08-27 19:23
40621	qerpzzea@gma ... (賽希爾 cecill(陳宥穎))	g598		233	2024-06-01 19:54
36815	fire5386 (becaidorz)	g598	題解 (不用二分搜)	534	2023-08-10 13:55