情報調查局內有 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。 | 由小到大輸出會形成矛盾的調查員編號，每個編號各自獨立一行。 |
| 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 | 2 |
| 5 2 0 3 2 3 3 2 0 2 2 4 0 1 1 2 3 4 2 4 | 1 3 |
解題思路
使用並查集的方式來做資料的存儲，當在收 2＊M 個 pair 的時候，跑一個函式來更新兩個全域陣列中的資料，兩個陣列分別為 friends 和 enemies，代表每一個人他的隊友和另外一組的人。在程式一開始時可以將兩個陣列從 0 到 N-1 分別預設為 -1。如果進函式時兩個人的 friends 陣列資料都是 -1，代表兩個人都沒有做過判斷，所以就將 friends 設為自己、enemies 設為另外一個人。如果兩個人的 friends 陣列資料都 != -1，代表兩個人都有判斷過，這邊要將兩個人所有的朋友和敵人都分別設置為新的朋友和敵人，下面的程式碼是使用函式的方式去做遞迴將每一個人的朋友、敵人設定為新的人。如果是其中一個人已經有資料另外一個人是 -1，則是將沒有資料的人的 friends 設定為另外一人的敵人的朋友根節點、enemies 設定為另外一個人的朋友根節點。
在判斷新的 pair 是否正確時也需要做資料的判斷，所以可以重新宣告一個 newFriend 和 newEnemy，並將 friends 和 enemies 的資料移過去，收到新的要判斷的 pair 時，要做的事情其實和上面的差不多，只是當兩個人的 newFriend 和 newEnemy 都有做過判斷時就不需要做判斷，跑完函式之後就是判斷 newFriend[a] 是否 == newFriend[b]。
範例程式碼－ZeroJudge G598: 真假子圖
#include <iostream>
using namespace std;
int friends[100000] = {}, enemies[100000] = {};
int newFriend[100000] = {}, newEnemy[100000] = {};
int findEnd(const int N) {
if (N == -1 || friends[N] == -1) return -1;
if (friends[N] == N) return N;
return findEnd(friends[N]);
}
int newFind(const int N) {
if (N == -1 || newFriend[N] == -1) return -1;
if (newFriend[N] == N) return N;
return newFind(newFriend[N]);
}
void meet(const int target, const int value) {
if (friends[target] == target) {
friends[target] = value;
return;
}
meet(friends[target], value);
friends[target] = value;
}
void kill(const int target, const int value) {
if (enemies[target] == target) {
enemies[target] = value;
return;
}
meet(enemies[target], value);
enemies[target] = value;
}
void people(const int a, const int b) {
if (friends[a] == -1 && friends[b] == -1) {
friends[a] = a;
friends[b] = b;
enemies[a] = b;
enemies[b] = a;
}
else if (friends[a] != -1 && friends[b] != -1) {
meet(a, findEnd(enemies[b]));
meet(b, findEnd(enemies[a]));
kill(a, findEnd(b));
kill(b, findEnd(a));
}
else {
if (friends[a] == -1) {
friends[a] = findEnd(enemies[b]);
enemies[a] = findEnd(b);
}
else {
friends[b] = findEnd(enemies[a]);
enemies[b] = findEnd(a);
}
}
}
void check(const int a, const int b) {
if (newFriend[a] == -1 && newFriend[b] == -1) {
newFriend[a] = a;
newFriend[b] = b;
newEnemy[a] = b;
newEnemy[b] = a;
return;
}
if (newFriend[a] != -1 && newFriend[b] != -1) return;
if (newFriend[a] == -1) {
newFriend[a] = newFind(newEnemy[b]);
newEnemy[a] = newFind(b);
return;
}
newFriend[b] = newFind(newEnemy[a]);
newEnemy[b] = newFind(a);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 0; i<N; i++) {
friends[i] = -1;
enemies[i] = -1;
}
for (int i = 0; i<M; i++) {
int a, b;
cin >> a >> b;
people(a, b);
}
int P, K;
cin >> P >> K;
for (int i = 1; i<=P; i++) {
bool window = false;
for (int j = 0; j<N; j++) {
newFriend[j] = -1;
newEnemy[j] = -1;
if (friends[j] != -1) newFriend[j] = friends[j];
if (enemies[j] != -1) newEnemy[j] = enemies[j];
}
for (int j = 0; j<K; j++) {
int a, b;
cin >> a >> b;
if (window) continue;
check(a, b);
if (newFind(a) == newFind(b)) {
window = true;
}
}
if (window) cout << i << "\n";
}
}
//ZeroJudge G598
//Dr. SeanXD