문제 출처

1. 문제설명

  • 팀을 구성하고자 한다.
  • 근데, 서로 같은 팀을 하기 싫어하는 사람들이 있다.
  • 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다.
  • 이를 만족하는 두 팀을 구하라


2. 알고리즘 설계

  • 이분 그래프를 알고, 문제를 읽는다면 로직이 한번에 떠오르는 문제이다.
  • BFS로 인접한 정점을 방문하면서 색을 칠한다.
  • 처음 방문하는 정점은 1로 칠한다.
  • 방문한 지점이면 아래 과정은 건너뛴다.
  • 이후 연결된 정점을 큐에 넣으면서, 현재 색상 * -1로 칠한다.
  • 이렇게 색을 반대로 칠해줌으로써 싫은 사람임을 파악할 수 있을 것이다.
  • 이후에는 -1인 그룹, 1인 그룹을 나눠 출력해주면 된다.


3. 전체 코드

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

const int SZ=105;
int n, cnt, tmp;
vector<int> adj[SZ];
vector<int> color;

void bfs() {
    for(int i=1; i<=n; i++) {
        if(color[i] != 0) continue;

        queue<int> q;
        q.push(i);
        color[i] = 1;

        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            for(int nxt : adj[cur]) {
                if(color[nxt] != 0) continue;
                color[nxt] = color[cur] * -1;
                q.push(nxt);
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    color.assign(n+1, 0);

    for(int i=1; i<=n; i++) {
        cin >> cnt;
        while(cnt--) {
            cin >> tmp;
            adj[i].push_back(tmp);
            adj[tmp].push_back(i);
        }
    }

    bfs();

    vector<int> blue;
    vector<int> red;

    for(int i=1; i<=n; i++) {
        if(color[i] == 1) blue.push_back(i);
        else red.push_back(i);
    }

    cout << blue.size() << '\n';
    for(int x : blue) cout << x << ' ';

    cout << '\n' << red.size() << '\n';
    for(int x : red) cout << x << ' ';

    return 0;
}