1953번 팀배분

 

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

 

이분 그래프 문제이다.

 

참고 문제 : https://www.acmicpc.net/problem/1707

참고 풀이 : https://hsdevelopment.tistory.com/74

 

 

#include<bits/stdc++.h>

using namespace std;

#define MAX 101

int N, M, T;
vector<int> v[MAX];
vector<int> a, b;
int color[MAX];

bool go(int now, int next)
{
    for (auto i : v[now]) {
        if (i == next) {
            return false;
        }
    }
    return true;
}

void dfs(int vertex, int nodeColor)
{
    color[vertex] = nodeColor;

    for (auto hateNode : v[vertex]) {
        if (color[hateNode] == 0) {
            dfs(hateNode, nodeColor * -1);
        }
    }
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    scanf("%d", &N);

    for (int i = 1; i <= N; i++) {
        int cnt = 0, hate = 0;
        scanf("%d", &cnt);
        for (int j = 0; j < cnt; j++) {
            scanf("%d", &hate);
            v[i].push_back(hate);
            v[hate].push_back(i);
        }
    }

    for (int i = 1; i <= N; i++) {
        if (color[i] == 0) {
            dfs(i, 1);
        }
    }

    printf("%d\n", count(color, color + MAX, 1));
    for (int i = 1; i <= N; i++) {
        if (color[i] == 1) {
            printf("%d ", i);
        }
    }
    printf("\n");

    printf("%d\n", count(color, color + MAX, -1));
    for (int i = 1; i <= N; i++) {
        if (color[i] == -1) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}