BOJ 23086 두 반으로 나누기

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/23086

🧐 관찰 및 접근
#

그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다.
- 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다.
- 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다.
  - 이때 시간 복잡도는 $O(K(N+M))$이다.
    - 이는 너무 느리다!
문제 상황을 조금 더 관찰해보자.
- $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다.
  - $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다!
    - **매개변수 탐색(파라메트릭 서치)**가 가능하다.

💻 풀이
#

코드 (C++):

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";
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#