1953 팀배분

#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
 
using namespace std;
 
vector<vector<int> > diff;
int team[105] = { 0 };    //-1, 1 두 팀으로 구분
 
void bfs(int idx) {
    queue<pair<int, int>> q;
 
    team[idx] = 1;
    q.push(make_pair(idx, 1));
 
    while (!q.empty()) {
        int cur = q.front().first;
        int t = q.front().second;
 
        q.pop();
 
        for (int i = 0; i < diff[cur].size(); i++) {
            int adv = diff[cur][i];
 
            if (team[adv] != 0)
                continue;
 
            team[adv] = -t;
            q.push(make_pair(adv, -t));
        }
    }
}
 
int main() {
    int t;
    scanf("%d", &t);
 
    diff.resize(t + 1);
 
    for (int i = 1; i <= t; i++) {
        int n;
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            int tmp;
            scanf("%d", &tmp);
 
            diff[i].push_back(tmp);
        }
    }
    
    for (int i = 1; i <= t; i++) 
        if (team[i] == 0) 
            bfs(i);
    
    vector<int> red;
    vector<int> blue;
    for (int i = 1; i <= t; i++) {
        if (team[i] == 1) 
            red.push_back(i);        
        if (team[i] == -1) 
            blue.push_back(i);        
    }
 
    printf("%d\n", red.size());
    for (int i = 0; i < red.size(); i++)
        printf("%d ", red[i]);
    printf("\n%d\n", blue.size());
    for (int i = 0; i < blue.size(); i++)
        printf("%d ", blue[i]);
}

레드블랙 트리를 연상시키는 풀이방식이었다

노드를 한칸씩 띄어서 갈때마다 다른 team 으로 배정한 다음에, 

맨 마지막에 서로 같은 팀끼리 정리해주는 방식을 취했다.

발상이 조금 필요했으나, 할만한 문제였다