1154번 : 팀 편성

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

1154번: 팀 편성

학생들을 주어진 조건에 따라 두 그룹으로 나누는 문제이다.

아이디어 : 

어떤 학생과 친구가 아니라는 것은, 무조건 그 친구와 다른 그룹이어야 한다는 것이다.
그렇다면, 답이 나오는 상황이라고 가정했을 때, 모든 학생에 대해서 해당 학생과 친구가 아닌 학생들을 전부 그룹으로 묶는 과정을 반복하면, 최종적으로는 두 그룹으로 나뉘어지게 될 것이다.
그 두 그룹에 대해 검증을 한번 더 하면, 조건에 맞는 두 그룹으로 나눌 수 있다.

구현 : 

Union-Find 알고리즘을 사용했다.

각 학생마다 친구가 아닌 학생들을 무조건 그룹으로 묶고, 이 과정을 전체 학생을 대상으로 반복한다.
일반적인 상황이면 두 그룹으로 묶이겠지만, 모든 친구들이 서로 친구이면 그룹이 하나도 생기지 않게 된다.
따라서 그룹으로 묶이지 않은 친구들은 그 친구들끼리 그룹으로 묶어준다.
이렇게 나온 그룹의 개수가 1개 또는 2개여야 한다.

다음으로 각 그룹에 대해 검증을 해보자. 그룹의 속한 임의의 학생 x는 그룹에 속한 다른 모든 학생들과 친구여야 한다.
검증이 끝나면 정렬을 한번 해주고, 답을 출력한다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
vector<int> G[1001];
int arr[1001][1001];
int p[1001];
void init(){
	for(int i=0; i<1001; ++i){
		p[i]=i;
	}
}
int find(int x){
	if(x==p[x]) return x;
	return p[x]=find(p[x]);
}
void unite(int a, int b){
	int A=find(a);
	int B=find(b);
	if(A==1) p[B]=A;
	else if(B==1) p[A]=B;
	else p[A]=B;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N; cin>>N;
	init();
	while(1){
		int a,b; cin>>a>>b;
		if(a==-1) break;
		G[a].push_back(b);
		G[b].push_back(a);
		arr[a][b]=1;
		arr[b][a]=1;
	}
	vector<int> v;
	for(int i=1; i<=N; ++i){
		v.clear();
		for(int j=1; j<=N; ++j){
			if(i==j) continue;
			if(!arr[i][j]) v.push_back(j);
		}
		for(int j=1; j<v.size(); ++j){
			unite(v[j-1], v[j]);
		}
	}
	int visit[1001]={0, };
	for(int i=1; i<=N; ++i){
		visit[find(i)]++;
	}
	v.clear();
	int cnt=0;
	for(int i=1; i<=N; ++i){
		if(visit[i]==1){
			v.push_back(i);
		}
		else if(visit[i]>1){
			cnt++;
		}
	}
	if(!v.empty()) cnt++;
	if(cnt>2){
		cout << "-1\n";
		return 0;
	}
	for(int i=1; i<v.size(); ++i){
		unite(v[i-1],v[i]);
	}
	vector<int> res1;
	vector<int> res2;
	for(int i=1; i<=N; ++i){
		if(find(i)==1) res1.push_back(i);
		else res2.push_back(i);
	}
	for(int i=0; i<res1.size(); ++i){
		for(int j=0; j<i; ++j){
			if(!arr[res1[i]][res1[j]]){
				cout << "-1\n";
				return 0;
			}
		}
	}
	for(int i=0; i<res2.size(); ++i){
		for(int j=0; j<i; ++j){
			if(!arr[res2[i]][res2[j]]){
				cout << "-1\n";
				return 0;
			}
		}
	}
	cout << "1\n";
	sort(res1.begin(), res1.end());
	sort(res2.begin(), res2.end());
	for(auto it:res1) cout << it << " ";
	cout << "-1\n";
	for(auto it:res2) cout << it << " ";
	cout << "-1\n";
}