백준8214 Party

작성일 | In

문제 링크

  • http://icpc.me/8214

문제 출처

  • 2010/2011 POI Stage3 2번

시간복잡도

*

풀이

3K개의 정점으로 이루어진 그래프가 있는데, 그중 2K개의 정점으로 이루어진 서브 그래프 중 하나는 완전 그래프입니다.
주어진 그래프에서 완전 그래프를 이루고 있는 K개의 정점을 출력하면 됩니다.

모든 정점 쌍을 보면서, 두 정점이 간선으로 연결되어 있지 않다면 두 정점을 모두 지워줍니다.
두 정점이 간선으로 연결되어 있지 않다는 것은 두 정점 중 최소 하나는 완전 그래프에 포함되지 않는 것을 의미합니다. 또한, 간선으로 연결되어 있지 않는 정점 쌍이 존재하지 않는다면, 그 그래프는 완전 그래프입니다.

3K개의 정점이 있을 때, 위 작업을 수행하면 최소 K개 이상의 정점이 남게 됩니다.
두 정점을 지울 때, 적어도 하나는 2K개의 정점으로 구성된 완전 그래프에 포함되지 않고, 그런 정점은 K개 있기 때문에 최대 K번 지우게 됩니다.
정점은 최대 2K개 지워지므로 마지막에 남는 정점은 최소 K개입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[3030][3030];
int chk[3030];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	while(m--){
		int s, e; cin >> s >> e;
		arr[s][e] = arr[e][s] = 1;
	}

	for(int i=1; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			if(!chk[i] && !chk[j] && !arr[i][j]){
				chk[i] = chk[j] = 1;
			}
		}
	}

	int cnt = 0;
	for(int i=1; i<=n; i++){
		if(cnt >= n/3) break;
		if(!chk[i]){
			cnt++; cout << i << " ";
		}
	}
}