2516번: 원숭이

https://www.acmicpc.net/problem/2516


$O(n)$

다음을 반복한다.
1. 원숭이 i를 보았을 때 자신의 원수들이 적은 팀으로 옮긴다.(같다면 옮기지 않는다.)
2. 옮겼다면 그 팀에 속한 원숭이들에 대해 1을 적용한다.
이 알고리즘이 선형시간 안에 끝남을 증명해보자.
1번에서 옮길 원숭이가 없다면 모든 원숭이에 대해 같은 팀에 원수가 1마리 이하임을 의미하므로 프로그램을 종료한다.
1번에서 옮기는 경우가 있다면 원수 관계가 1개 이상 줄어들고 이러한 상황은 많아야 3n 번 가능하다.
증명 끝.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e5;
int n, m, t[MXN + 1], tc[2];
vector<int> adj[MXN + 1];
queue<int> q;
int main() {
    scanf("%d", &n);
    tc[0] = n;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &m);
        for (int j = 0; j < m; j++) scanf("%d", &x), adj[i].push_back(x);
        q.push(i);
        while (!q.empty()) {
            int h = q.front(), c = 0;
            for (auto it : adj[h]) c += t[h] ^ t[it] ? -1 : 1;
            if (c > 0) {
                for (auto it : adj[h]) q.push(it);
                tc[t[h]]--; t[h] = !t[h]; tc[t[h]]++;
            }
            q.pop();
        }
    }
    for (int i = 0; i<2; i++) {
        printf("%d ", tc[i]);
        for (int j = 1; j <= n; j++) if (t[j] == i) printf("%d ", j);
        puts("");
    }
    return 0;
}