[백준] 1953 팀배분

문제

2007년 1월 9일(화)는 원장선생님의 말씀대로 어제와 같이 하루 일과를 팀플레이를 통해 하려고 한다. 이 날은 특별히 청팀과 백팀으로 두 팀을 나누어 팀전을 하려 한다. 하지만 어제 하루 팀플레이를 하면서, 서로 같은 팀을 하기 싫어하는 사람들이 생겼다.

이제 우리가 할 일은 다음과 같다. 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 그 사람들의 요구를 수용하여 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다. 이 조건을 만족하여 n명의 사람들 두 팀으로 나누는 프로그램을 작성하여라.

입력

첫 줄에는 학생들의 수 n (1 ≤ n ≤ 100)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 서로가 싫어하는 사람들의 정보가 주어진다. i+1번째 줄에는 i번째 사람이 싫어하는 사람의 수와 싫어하는 사람들이 나온다.

모든 사람이 싫어하는 사람이 단 한 명도 없는 경우는 없다.

출력

첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속한 사람들을 출력한다. 단 답이 여러 가지 일 경우에는 한 가지만 출력하여도 좋다.

 

싫어하는 사람과 팀을하면 안됩니다.

1번부터 N번사람까지 팀이 정해지지 않은 사람대로 BFS를 수행합니다.

큐에서 탑을 기준으로 싫어하는사람을 모두 반대편 팀에 넣습니다.

방문표시를하면서 모든 사람들이 방문될때까지 수행합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int N, v[101];
vi adj[101];
vi team[2];
int toggle(int k) {
	return k == 1 ? 0 : 1;
}
int main() {
	FAST;
	cin >> N;
	REP(i, N) {
		int n, x;
		cin >> n;
		while (n--) {
			int a;
			cin >> a;
			adj[i].push_back(a);
			adj[a].push_back(i);
		}
	}
	REP(i, N) { //1번부터 N번째 사람까지 BFS를 수행합니다.
		if (!v[i]) { //i번째 사람의 팀이 정해지지 않았으면
			v[i] = 1; //방문표시
			team[0].push_back(i); //0번팀으로 가정
			queue<pi>q;
			q.push({i,0});//BFS
			while (!q.empty()) {
				auto [cur, t] = q.front();
				q.pop();
				for (auto r : adj[cur]) {
					if (!v[r]) {
						v[r] = 1;
						q.push({r,toggle(t)}); 
						team[toggle(t)].push_back(r); //모든 자식을 반대팀에 넣습니다
					}
				}
			}
		}
	}
	sort(team[0].begin(), team[0].end());
	sort(team[1].begin(), team[1].end());
	cout << team[0].size() << "\n";
	for (auto r : team[0]) {
		cout << r << " ";
	}
	cout << "\n" << team[1].size() << "\n";
	for (auto r : team[1]) {
		cout << r << " ";
	}
}