📝 문제 정보
🧐 관찰 및 접근
- 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다.
- 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다.
- 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다.
- 이때 시간 복잡도는 $O(K(N+M))$이다.
- 문제 상황을 조금 더 관찰해보자.
- $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다.
- $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다!
- **매개변수 탐색(파라메트릭 서치)**가 가능하다.
💻 풀이
int N, M, K;
vector<pair<int, int>> links[100010]; // (nxt, idx)
vector<int> prohibit_list;
int color[100010]; // 0: unvisited, 1: group A, 2: group B
bool prohibited[200010];
bool isBipartite(int cnt){
rep(i, 1, M+1) prohibited[i] = false;
rep(i, 0, cnt) prohibited[prohibit_list[i]] = true;
rep(i, 1, N+1) color[i] = 0;
rep(i, 1, N+1) if(color[i] == 0){
queue<int> Q;
Q.push(i);
color[i] = 1;
while(!Q.empty()){
int cur = Q.front(); Q.pop();
for(auto [nxt, idx]: links[cur]){
if(prohibited[idx]) continue;
if(color[nxt] == 0){
color[nxt] = (color[cur] == 1 ? 2 : 1);
Q.push(nxt);
}
else if(color[nxt] == color[cur]){
return false;
}
}
}
}
return true;
}
void solve(){
cin >> N >> M >> K;
rep(i, 1, M+1){
int u, v; cin >> u >> v;
links[u].push_back({v, i});
links[v].push_back({u, i});
}
rep(i, 0, K){
int p; cin >> p;
prohibit_list.push_back(p);
}
// 모두 금지했을때 이분 그래프인가?
if(!isBipartite(K)){
cout << -1;
return;
}
// 파라메트릭 서치
int ok = K, ng = -1;
while(ok - ng > 1){
int mid = (ok + ng) >> 1;
if(isBipartite(mid)) ok = mid;
else ng = mid;
}
cout << ok << "\n";
int groupA_sz = 0, groupB_sz = 0;
isBipartite(ok);
rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++;
cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n";
}