7 - 38 그림 착색 문제 (25 점) (set)

7-38 착색 문제 (25 분)
그림 착색 문 제 는 유명한 NP 완전 문제 다.방향 없 는 그림 G = (V, E) 을 지정 합 니 다. K 색 으로 V 의 모든 정점 에 한 가지 색 을 분배 하여 두 개의 인접 한 정점 이 같은 색 을 가지 지 않도록 할 수 있 습 니까?
그러나 이 문 제 는 착색 문 제 를 해결 하 라 는 것 이 아니 라 주어진 색상 에 대한 배분 입 니 다. 착색 문 제 를 푸 는 것 인지 아 닌 지 판단 하 세 요.
입력 형식:
첫 줄 에 입력 하여 정수 V 3 개 (0)
출력 형식:
각 색상 배분 방안 에 대해 그림 착색 문제 의 풀이 라면 출력 Yes, 그렇지 않 으 면 출력 No 이 한 줄 을 차지한다.
입력 예시:
6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

출력 예시:
Yes
Yes
No
No

코드:
#include
#include
#include
using namespace std;
struct node{
	int x,y;
}s[250005]; 
int num[505];
int v,e,k;
int n;
int main()
{
	cin>>v>>e>>k;
	for(int i=1;i<=e;i++)
	{
		scanf("%d%d",&s[i].x,&s[i].y);
	}
	cin>>n;
	set t;
	while(n--)
	{
		t.clear();
		for(int i=1;i<=v;i++)
		{
			scanf("%d",&num[i]);
			t.insert(num[i]);
		}
		if(t.size()!=k)
		    cout<

좋은 웹페이지 즐겨찾기