# APCS實作題2021年11月第4題：真假子圖
> 日期：2024年8月27日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g598)
<br />
## 題目
### 問題描述
情報調查局內有 $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$ 分組吻合。
<br />
### 輸入格式
第一行先輸出兩個正整數 $n$ 和 $m$。
第二行有 $2m$ 個非負整數兩兩形成一個數對，表示目前還留存的 $m$ 個 pair。
第三行有兩個正整數 $p$ 和 $k$。
並且接下來的 $p$ 行每行有 $2k$ 個非負整數, 兩兩形成一對代表某個調查員找到的 $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,~ ans = 1$
- 20%：$1 \leq n, m \leq 5000,~ 1 \leq p \leq 200$
- 60%：無額外限制
<br />
### 輸出格式
由小到大輸出會形成矛盾的調查員編號，每個編號各自獨立一行。
<br />
### 範例輸入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
```
5 2
0 3 2 3
3 2
0 2 2 4
0 1 1 2
3 4 2 4
```
### 範例輸出2
```
1
3
```
<br />
## Python 程式碼
費時最久約 3.4 s，使用記憶體最多 41 MB，通過測試。
```python=
def BFS(G, color, s): # 廣度優先走訪，輸入圖 G、顏色 color、起點 s
color[s] = 1 # 指定起點顏色為 1
que = [s] # 要走訪的節點，先放入起點 s
head = 0 # 從 que 讀資料用的索引值
while head < len(que):
u = que[head]; head += 1 # 從 que 取出節點 u，head 加 1
for v in G[u]: # 依序取出與 u 相連的節點
if color[v] == color[u]: # 如果顏色相同，不是二分圖
return False # 回傳 Fasle
if color[v] == 0: # 節點 v 未走訪
color[v] = -color[u] # 填上另一種顏色
que.append(v) # 將 v 加入 que
return True # 結束 while 迴圈，是二分圖，回傳 True
def bipar(G, num): # 檢測是否為二分圖 bipartite graph，相連節點要是不同的顏色
color = [0]*num # 兩種顏色 -1, 1，0 代表未檢測
for i in range(num): # 有 n 個點要檢測
if color[i] == 0: # 如果這個點未檢測
if not BFS(G, color, i): # 用 BFS 檢測
return False # 回傳 Fasle
return True # 結束 for 迴圈，是二分圖，回傳 True
n, m = map(int, input().split()) # 共有 n 對，目前剩下 m 對
d = list(map(int, input().split())) # 目前剩下的配對資料
graph = [[] for _ in range(n)] # 無向圖
for i in range(0, 2*m, 2): # 將目前剩下的配對資料填入圖中
graph[d[i]].append(d[i+1])
graph[d[i+1]].append(d[i])
p, k = map(int, input().split()) # p 個調查員，各回傳 k 對資料
gi = [] # 暫存調查員回傳資料的串列
for _ in range(p): # 讀取 p 行資料
gi.append(list(map(int, input().split())))
st = [[0, p-1]] # 要檢測的範圍
ans = [] # 儲存答案用的串列
while st: # 如果 st 還有資料，繼續執行
left, right = st.pop() # 由 st 取出左、右端點
Graph = [e.copy() for e in graph] # 複製 graph 的資料，不能直接用 graph.copy()
for i in range(left, right+1): # 檢測 [left, right] 範圍
for j in range(0, 2*k, 2): # 由 gi 讀取配對資料加入 Graph
Graph[gi[i][j]].append(gi[i][j+1])
Graph[gi[i][j+1]].append(gi[i][j])
if not bipar(Graph, n): # 如果不是二分圖
if left == right: ans.append(left+1) # 如果左、右端點相等，找到答案，將編號 left+1 加入 ans
else:
mid = (right - left) // 2 + left # 取中點
st.append([left, mid])
st.append([mid+1, right])
# 結束 while 迴圈
ans.sort() # 由小到大排序
for x in ans: print(x) # 印出答案
```
<br /><br />
## C++ 程式碼
費時最久約 0.3 s，使用記憶體最多 6.7 MB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
/* 廣度優先走訪，輸入圖 G、顏色 color、起點 s */
bool BFS(vector<vector<int>>& G, vector<int>& color, int s) {
color[s] = 1; // 指定起點顏色為 1
stack<int> st; st.push(s); // 要走訪的節點，先放入起點 s
while(!st.empty()) { // 如果 st 還有節點繼續執行
int u = st.top(); st.pop(); // 從 st 最上面取出並移除節點
for(int v : G[u]) { // 依序取出與 u 相連的節點
if (color[v] == color[u]) return false; // 如果顏色相同，不是二分圖，回傳 fasle
if (color[v] == 0) { // 節點 v 未走訪
color[v] = -color[u]; // 填上另一種顏色
st.push(v); // 將 v 加入 st
}
}
}
return true; // 結束 while 迴圈，是二分圖，回傳 true
}
/* 檢測是否為二分圖 bipartite graph，相連節點要是不同的顏色 */
bool bipar(vector<vector<int>>& G, int num) {
vector<int> color (num, 0); // 兩種顏色 -1, 1，0 代表未檢測
for(int i=0; i<num; i++) { // 有 n 個點要檢測
if (color[i] == 0) // 如果這個點未檢測
if (!BFS(G, color, i)) // 用 BFS 檢測，如果不是二分圖
return false; // 回傳 Fasle
}
return true; // 結束 for 迴圈，是二分圖，回傳 True
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
int n, m; cin >> n >> m; // 共有 n 對，目前剩下 m 對
vector<vector<int>> graph (n, vector<int> ()); // 無向圖
for(int i=0; i<m; i++) { // 將目前剩下的配對資料填入圖中
int a, b; cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int p, k; cin >> p >> k; // p 個調查員，各回傳 k 對資料
vector<vector<int>> gi (p, vector<int> (2*k)); // 暫存調查員回傳資料的串列
for(int i=0; i<p; i++) { // 讀取 p 行資料
for(int j=0; j<2*k; j+=2) {
cin >> gi[i][j] >> gi[i][j+1];
}
}
stack<pair<int, int>> st; // 要檢測的範圍
st.push(make_pair(0, p-1)); // 先放入 {0, p-1}
vector<int> ans; // 儲存答案用的陣列
while(!st.empty()) { // 如果 st 還有資料，繼續執行
int left = st.top().first, right = st.top().second; st.pop(); // 由 st 最上面取出並移除左、右端點
vector<vector<int>> Graph (graph.begin(), graph.end()); // 複製 graph 的資料
for(int i=left; i<=right; i++) { // 檢測 [left, right] 範圍
for(int j=0; j<2*k; j+=2) { // 由 gi 讀取配對資料加入 Graph
Graph[gi[i][j]].push_back(gi[i][j+1]);
Graph[gi[i][j+1]].push_back(gi[i][j]);
}
}
if (!bipar(Graph, n)) { // 如果不是二分圖
if (left == right) ans.push_back(left+1); // 如果左、右端點相等，找到答案，將編號 left+1 加入 ans
else {
int mid = (right - left) / 2 + left; // 取中點
st.push(make_pair(left, mid));
st.push(make_pair(mid+1, right));
}
}
}
sort(ans.begin(), ans.end()); // 由小到大排序
for(auto a : ans) cout << a << "\n"; // 印出答案
return 0;
}
```
<br /><br />
## 參考資料
吳邦一教授的 APCS 解題影片〈[PyAp45 Python APCS 題解：病毒演化(AP202007_4), ZeroJudge f582](https://youtu.be/CzUCI2d1ER0?si=0PlLXicX4uIZeKSU)〉
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet