# 【題解】ZeroJudge g598: 4. 真假子圖

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=g598
【解題想法】DFS，二分搜

```#include <bits/stdc++.h>
using namespace std;

int n, m, p, k, color[20005];
vector <int> now[20005];
vector <pair<int, int> > e, v[10005];

bool dfs(int x, int pre){
for (int i:now[x]){
if (i == pre) continue;
if (!color[i]){
color[i] = 3-color[x];
if (!dfs(i, x)) return false;
}
else if (color[i] == color[x]) return false;
}
return true;
}

bool check(int x){
for (int i = 1; i <= n; i++){
color[i] = 0;
now[i].clear();
}
for (auto i:e){
now[i.first].push_back(i.second);
now[i.second].push_back(i.first);
}
for (int i = 1; i <= x; i++){
for (auto j:v[i]){
now[j.first].push_back(j.second);
now[j.second].push_back(j.first);
}
}
for (int i = 1; i <= n; i++){
if (!color[i]){
color[i] = 1;
if (!dfs(i, 0)) return false;
}
}
return true;
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0, x, y; i < m; i++){
cin >> x >> y;
x++;
y++;
e.push_back({x, y});
}
cin >> p >> k;
for (int i = 1, x, y; i <= p; i++){
for (int j = 0; j < k; j++){
cin >> x >> y;
x++;
y++;
v[i].push_back({x, y});
}
}
int l = 0, r = p;
for (int i = 0; i < 3; i++){
while (r-l > 1){
int mid = (l+r)/2;
if (check(mid)) l = mid;
else r = mid;
}
cout << r << "\n";
v[r].clear();
l = r;
r = p;
if (check(p)) break;
}
}
```