백준 1953

문제

풀이

결국 이분그래프를 만드는 문제다.

 

5
1 3
1 5
2 1 4
1 3
1 2

의 경우를 예로 들자.

 

싫어하는 관계를 유향그래프로 그리면 이렇게 나타낼 수 있다.

 

여기서 1번노드부터 청팀에 들어간다고 가정하자. 그렇게 된다면 1번 노드는 3번을 싫어하므로 3번은 무조건 백팀에 들어가게 된다.

 

3번을 기준으로 3번노드는 4번을 싫어하므로 4번노드는 청팀에 들어가게 된다.

 

4번노드는 싫어하는 노드가 없으므로, 다시 2번노드부터 청팀에 넣고 시작하게 된다면

 

다음과 같은 그래프가 그려지게 된다.

 

싫어하는 사람이 하나도 없는 경우는 없으므로, 한명만 싫어하는사람이 한명 있는 경우가 탐색의 기준에서 가장 오래 걸리는 경우다.

 

모든 노드를 한번씩만 방문하면 되므로 O(N)이다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int> > v(101);
int n, vis[101], blue[101], white[101], bans, wans;

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        int a; cin>>a;
        while(a--) {
            int b; cin>>b;
            v[i].push_back(b);
        }
    }
    for(int i=1; i<=n; i++) {
        if(vis[i]) continue;
        vis[i] = 1;
        blue[i] = 1; bans += 1;
        queue<int>q;
        q.push(i);
        while(!q.empty()) {
            int cur = q.front(); q.pop();
            for(auto e : v[cur]) {
                if(vis[e]) continue;
                vis[e] = 1;
                if(blue[cur]) {
                    white[e] = 1;
                    wans += 1;
                }
                if(white[cur]) {
                    blue[e] = 1;
                    bans += 1;
                }
                q.push(e);
            }
        }

    }
    cout<<bans<<'\n';
    for(int i=1; i<=n; i++)
        if(blue[i]) cout<<i<<' ';
    cout<<'\n';
    cout<<wans<<'\n';
    for(int i=1; i<=n; i++)
        if(white[i]) cout<<i<<' ';

}