1953번: 팀배분

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

$O(n)$

dfs를 통해 홀수 번째 방문시 1, 짝수 번째 방문시 2로 표시한다.

#include<cstdio>
#include<vector>
using namespace std;
int n, c[101], cnt[3];
vector<int> adj[101];
void f(int h, int s) {
        if (c[h]) return;
        c[h] = s;
        cnt[s]++;
        for (auto it : adj[h]) f(it, 3 - s);
}
int main() {
        scanf("%d", &n);
        for (int i = 1, m, x; i <= n; i++)
            for (scanf("%d", &m); m--;) scanf("%d", &x), adj[i].push_back(x);
        for (int i = 1; i <= n; i++) f(i, 1);
        printf("%d\n", cnt[1]);
        for (int i = 1; i <= n; i++) if (c[i] == 1) printf("%d ", i);
        printf("\n%d\n", cnt[2]);
        for (int i = 1; i <= n; i++) if (c[i] == 2) printf("%d ", i);
        return 0;
}