BOJ 1154 팀 편성

📝 문제 정보

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

🧐 관찰 및 접근

A / B팀으로 나누는걸 보면 당연히 이분그래프를 떠올릴 수 있겠는데..
- 같은 그룹의 학생들끼리는 모두 서로 아는 사이여야 한다?
- 우리가 아는 이분그래프의 정의랑 뭔가 느낌이 다르다!
저 말을 다시한번 생각해보자
- 같은 그룹의 학생이다 -> 서로 아는사이이다
- 이 문장의 대우명제는?
  - 서로 모르는 사이이다 -> 다른 그룹의 학생이다
- 그렇다면, 그래프의 간선을 뒤집어버리자!
  - $N$은 최대 1000이므로, 간선 $M = N^2$개는 충분히 계산할 수 있다.
  - 이렇게 간선을 뒤집은 그래프를 여 그래프, 혹은 complement graph라고 한다.

💻 풀이

코드 (C++):

void solve(){
    cin >> N;
    while(1){
        int u, v; cin >> u >> v;
        if(u == -1 && v == -1) break;
        know[u][v] = know[v][u] = true;
    }

    bool isBipartite = true;
    vector<int> color(N+1, 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();
            rep(nxt, 1, N+1){
                if(cur == nxt) continue;
                if(know[cur][nxt]) continue;
                if(color[nxt] == 0){
                    color[nxt] = (color[cur] == 1 ? 2 : 1);
                    Q.push(nxt);
                }
                else if(color[nxt] == color[cur]){
                    isBipartite = false;
                    break;
                }
            }
        }
    }
    if(!isBipartite){
        cout << -1;
        return;
    }
    vector<int> team1, team2;
    rep(i, 1, N+1){
        if(color[i] == 1) team1.push_back(i);
        else team2.push_back(i);
    }

    cout << 1 << "\n";
    for(auto x: team1) cout << x << " "; cout << -1 << "\n";
    for(auto x: team2) cout << x << " "; cout << -1 << "\n";
}