[코드업] 4763 - 원숭이

KOI 동물원에는 N마리의 원숭이가 있고, 이 원숭이들을 수용할 수 있는 두 개의 큰 우리가 있다. 모든 원숭이들은 1부터 N 까지의 번호가 매겨져 있다.

원숭이들 사이에는 유달리 서로 앙숙관계인 원숭이들이 있어서 같은 우리에 두었을 경우 서로 싸우는 경우가 많다. 두 원숭이 x와 y가 앙숙관계라는 것은 두 원숭이 x, y가 서로 싫어하는 관계임을 의미한다. 또한, 각각의 한 원숭이에 대해 앙숙관계에 있는 원숭이들의 수는 기껏해야 세 마리라고 가정한다. 동물원에서는 원숭이들의 앙숙관계를 조사하여 아래의 두 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하려고 한다.

• (조건 1) 각 원숭이에 대해 같은 우리 안에 있으며 앙숙관계인 원숭이는 한 마리 이하이다.
• (조건 2) 비어있는 우리는 없다. (즉, 하나의 우리에 원숭이를 모두 수용 가능한 경우가 있더라도 각각의 우리에는 적어도 한 마리 이상의 원숭이를 수용하여야 한다.)

예를 들어, N = 5 인 경우에 1번 원숭이는 {2, 3, 4}와 2는 {1, 3, 5}와 앙숙관계이고, 그리고 3은 {1, 2, 4}와 4는 {1, 3, 5}, 그리고 5는 {2, 4}와 앙숙관계라고 하자. 위의 조건을 만족하도록 원숭이들을 두 개의 우리로 나누려면 {1, 3, 5}를 하나의 우리에, 그리고 {2, 4}를 다른 우리에 수용하면 된다.

원숭이들의 수와 각 원숭이들의 앙숙관계가 입력으로 주어질 때, 위의 조건을 만족하도록 원숭이들을 두 개의 우리에 나누어 수용하는 프로그램을 작성하시오.

입력 예시

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

출력 예시

1 3 5
2 4

---

#include<iostream>
#include<vector>
using namespace std;

int main(){
	int N;
	cin >> N;

	vector<vector<int>> monkey(N);

	int M;
	for(int i = 0; i < N; i++){
		cin >> M;

		int angsuk;
		for(int j = 0; j < M; j++){
			cin >> angsuk;
			monkey[i].push_back(angsuk - 1);
		}
	}

	vector<bool> cage1(N, true), cage2(N, false);

	bool flag = false;
	while(true){
		flag = true;
		for(int i = 0; i < N; i++){
			if(cage1[i]){
				int count = 0;
				for(int elem : monkey[i]){
					if(cage1[elem])
						count++;
				}
				if(count > 1){
					cage1[i] = false;
					cage2[i] = true;
					flag = false;
				}
			}
		}
		if(flag) break;

		flag = true;
		for(int i = 0; i < N; i++){
			if(cage2[i]){
				int count = 0;
				for(int elem : monkey[i]){
					if(cage2[elem])
						count++;
				}
				if(count > 1){
					cage1[i] = true;
					cage2[i] = false;
					flag = false;
				}
			}
		}
		if(flag) break;
	}

	for(int i = 0; i < N; i++){
		if(cage1[i])
			cout << i + 1 << " ";
	}
	cout << '\n';
	for(int i = 0; i < N; i++){
		if(cage2[i])
			cout << i + 1 << " ";
	}

	return 0;
}