真假子圖 題解｜APCS 2021 年 11 月高級 第 4 題
前置知識
這題是「二分圖判定」加上「每份報告獨立判斷、但不能每次從頭做」，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：
- 二分圖與二染色：NTUCPC Guide〈二分圖〉——「每條邊兩端不同色」做不做得到，等於圖裡有沒有奇環；用 DFS 或 BFS 一邊走一邊塗相反的顏色，撞到同色就失敗。
- BFS 與連通塊：NTUCPC Guide〈廣度優先搜尋〉、吳邦一《AP325》7.2.2（教材 PDF 第 225～228 頁）——圖可能不連通，每個還沒碰過的點都要重新當一次起點。
- 會用到的語法：巢狀
vector當鄰接串列、pair。
簡潔題意
\(n\) 個人分成兩個陣營，已知 \(m\) 對「這兩人不同陣營」的關係（保證彼此相容）。\(p\) 位調查員各自提出 \(k\) 對不同陣營的關係；對每一位，只把他那 \(k\) 對加進已知關係，問還能不能把所有人分成兩個陣營，依編號印出做不到的調查員（\(1 \le n, m \le 20000\)，\(2 \le p \le 10000\)，\(1 \le k \le 20\)；不合法的調查員有 \(1\) 到 \(3\) 位）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(20\) 分）：\(n, m \le 100\)，\(p \le 20\)，恰有一位不合法。
- 子題組 2（\(20\) 分）：\(n, m \le 5000\)，\(p \le 200\)。
- 子題組 3（\(60\) 分）：無額外限制。
先拿下 40 分：每位調查員重建一次圖，BFS 二染色
關係是邊、陣營是顏色、有關係的兩人顏色要不同——能不能分成兩個陣營，就是這張圖是不是二分圖。最直接的做法：對每位調查員，把已知的 \(m\) 條邊加上他的 \(k\) 條邊重新建一張圖，BFS 塗色，塗到某條邊兩端同色就是矛盾。圖可能不連通，所以每個還沒塗色的點都要當一次起點。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> known(m); // 已知的「不同陣營」關係
for (int i = 0; i < m; i++) cin >> known[i].first >> known[i].second;
int p, k;
cin >> p >> k;
for (int id = 1; id <= p; id++) {
vector<vector<int>> adj(n); // 每位調查員都從已知關係重新建圖
for (int i = 0; i < m; i++) {
adj[known[i].first].push_back(known[i].second);
adj[known[i].second].push_back(known[i].first);
}
for (int i = 0; i < k; i++) { // 先把 k 對關係全部讀完，再開始判斷
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> camp(n, -1); // 0／1 兩個陣營，-1＝還沒分配
bool ok = true;
for (int s = 0; s < n && ok; s++) { // 圖可能不連通：每一塊都要染
if (camp[s] != -1) continue;
camp[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty() && ok) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (camp[v] == -1) {
camp[v] = 1 - camp[u]; // 有關係的兩人一定在不同陣營
q.push(v);
} else if (camp[v] == camp[u]) {
ok = false; // 兩端已經同陣營：矛盾
}
}
}
}
if (!ok) cout << id << '\n';
}
return 0;
}
讀入時先把 \(k\) 對關係全部讀完再判斷——一發現矛盾就跳出讀入迴圈，剩下的數字會被當成下一位調查員的資料。每位調查員 \(O(n + m + k)\)，子題組 1、2 的 \(p \le 200\) 瞬間跑完；子題組 3 的 \(p = 10000\) 要重建一萬次圖，本站實測 \(14\)～\(16\) 秒，時限 \(2\) 秒。
從 40 分到 100 分：已知關係只染一次，調查員只在「連通塊」之間檢查
重建一萬次圖，但已知的那 \(m\) 條邊每次都一樣——先把它們染好色、存起來。題目保證已知關係彼此相容，所以染得出來；染完每個人有一個陣營 camp（\(0\) 或 \(1\)）和一個連通塊編號 comp。關鍵觀察有兩條：
- 同一個連通塊裡，任兩人的顏色關係是固定的：\(a\)、\(b\) 同塊又同色，不管怎麼分陣營都同陣營，調查員說他們不同陣營就是直接矛盾。
- 不同連通塊之間沒有任何約束：每一塊可以整塊「翻面」（\(0\) 變 \(1\)、\(1\) 變 \(0\)），翻不翻面各塊獨立。
所以一位調查員的每一對 \((a, b)\) 分成兩種：同塊的，同色就矛盾、異色就沒事；不同塊的，變成一條「兩塊翻面要不要不同」的要求——\(a\)、\(b\) 現在同色，兩塊就要翻得不一樣才分得開；現在異色，就要翻得一樣（都翻或都不翻）。這些要求構成一張最多 \(2k\) 個點（連通塊）、\(k\) 條邊的小圖，每條邊標著「要相同」或「要不同」，再做一次像 BFS 染色一樣的事：走到一塊就決定它翻不翻，照邊上的要求推給鄰塊，推到一塊已經決定過、而且跟要求不合，就是矛盾。圖 1 用範例 2 走一遍。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
// 已知關係只染一次：camp 是陣營（0／1）、comp 是連通塊編號
vector<int> camp(n, -1), comp(n, -1);
int groups = 0;
for (int s = 0; s < n; s++) {
if (camp[s] != -1) continue;
camp[s] = 0;
comp[s] = groups;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (camp[v] != -1) continue; // 題目保證已知關係彼此相容，這裡不會矛盾
camp[v] = 1 - camp[u];
comp[v] = groups;
q.push(v);
}
}
groups++;
}
int p, k;
cin >> p >> k;
vector<vector<pair<int, int>>> small(groups); // 連通塊之間的限制：(另一塊, 兩塊翻面與否要不要不同)
vector<int> flip(groups, -1); // 這一塊要不要整塊翻面；-1＝還沒決定
for (int id = 1; id <= p; id++) {
vector<int> touched; // 這位調查員碰到的連通塊，用完要清乾淨
bool ok = true;
for (int i = 0; i < k; i++) { // 一樣先把 k 對關係讀完
int a, b;
cin >> a >> b;
int ca = comp[a], cb = comp[b];
int need = (camp[a] == camp[b]) ? 1 : 0; // 現在同陣營：兩塊的翻面要「不同」才分得開
if (ca == cb) {
if (need == 1) ok = false; // 同一塊裡的兩人同陣營：怎麼翻都分不開
continue;
}
small[ca].push_back({cb, need});
small[cb].push_back({ca, need});
touched.push_back(ca);
touched.push_back(cb);
}
// 在「連通塊的小圖」上決定每一塊翻不翻：和上面的染色一樣，只是邊上多了「要相同／要不同」
for (int s : touched) {
if (!ok) break;
if (flip[s] != -1) continue;
flip[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty() && ok) {
int u = q.front();
q.pop();
for (int t = 0; t < (int)small[u].size(); t++) {
int v = small[u][t].first, need = small[u][t].second;
if (flip[v] == -1) {
flip[v] = flip[u] ^ need; // need = 1 就翻得不一樣，0 就一樣
q.push(v);
} else if (flip[v] != (flip[u] ^ need)) {
ok = false; // 兩條路要求的翻法不一樣：矛盾
}
}
}
}
if (!ok) cout << id << '\n';
for (int c : touched) { // 只清這次碰到的塊，不用清整個陣列
small[c].clear();
flip[c] = -1;
}
}
return 0;
}
已知關係染色 \(O(n + m)\) 只做一次；每位調查員只碰他那 \(k\) 條邊牽到的連通塊，小圖的邊和翻面紀錄用 touched 清單只清這次碰到的，不去清整個陣列，總共 \(O(n + m + pk)\)，\(n = m = 20000\)、\(p = 10000\) 本站實測 \(0.09\) 秒。翻面用 XOR 推：flip[v] = flip[u] ^ need，need = 1 翻得不一樣、need = 0 翻得一樣。
測過再交：範例沒有「不同塊、同顏色、但合法」的對照
兩個範例蓋到了同塊同色的直接矛盾（範例 1 的 0–3、範例 2 的 0–2）、新關係之間繞出奇環（範例 2 的調查員 3）、翻面後合法（範例 2 的調查員 2）。沒蓋到：最小輸入、只靠「染色固定」會誤判的局面、矛盾出現在報告中間、同一位調查員重複提同一對。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
2 1 ／ 0 1 ／ 2 1 ／ 0 1 ／ 0 0 |
2 |
最小輸入；自己跟自己不同陣營一定矛盾 |
4 1 ／ 0 1 ／ 2 2 ／ 0 2 2 1 ／ 0 2 1 3 |
1 |
調查員 1 的兩對自己繞出三角形；只逐對跟已知關係比會什麼都不印 |
4 2 ／ 0 1 2 3 ／ 3 1 ／ 0 2 ／ 1 3 ／ 0 0 |
3 |
\(0\)、\(2\) 染出來同色但不同塊，翻一塊就合法；把染色當固定會印 1、2、3 |
3 1 ／ 0 1 ／ 2 3 ／ 0 2 2 2 1 2 ／ 0 2 0 2 0 2 |
1 |
矛盾在報告中間：一發現就 break 會把剩下的 1 2 讀給調查員 2，印 1、2 |
3 1 ／ 0 1 ／ 3 2 ／ 0 2 1 2 ／ 0 2 0 2 ／ 1 2 1 2 |
1 |
調查員 1 不合法之後，2、3 要從乾淨的狀態重判；圖沒重建會印 1、2、3 |
用程式造：\(n = 20000\) 的鏈 0 1 1 2 … 19998 19999、\(p = 10000\)、\(k = 20\)，前 \(9999\) 位各提 \(20\) 對鏈上相鄰的兩人、第 \(10000\) 位提 \(20\) 次 0 2 |
10000 |
子題組 3 的規模：每位調查員重建圖本站實測 \(13\) 秒 |
六筆都親眼看過正確，這題就穩了。
常犯錯誤
- 把已知關係染出來的顏色當成固定的：忘了每個連通塊可以整塊翻面，不同塊的兩人只要同色就報矛盾。範例 1 印
1、2，範例 2 印1、2、3；本站測資掛 \(2\) 筆。 - 只逐對檢查新關係跟已知關係衝不衝：新關係之間也會湊出奇環（範例 2 的調查員 3 是
3 4、2 4兩對合起來才矛盾），範例 2 只印1；本站測資掛 \(10\) 筆。 - 上一位調查員的東西沒清乾淨：40 分版沒重建圖、或 100 分版小圖的邊與翻面紀錄留到下一位——範例 2 的調查員 1 不合法之後，2、3 跟著被拖下水，範例 2 印
1、2、3（翻面紀錄沒清的那種則是只印1）；本站測資分別掛 \(20\) 筆／\(10\) 筆。 - 一發現矛盾就
break跳出讀入迴圈：那位調查員剩下的數字被當成下一位的資料，範例 2 只印1（調查員 3 的資料被吃掉一對）；自測表第 4 列專抓，本站測資掛 \(2\) 筆。 - 每位調查員都重建整張圖：子題組 3 本站實測 \(14\)～\(16\) 秒，只有 \(40\) 分。