7 - 38 그림 착색 문제 (25 점) (set)
1101 단어 데이터 구조 - STL
그림 착색 문 제 는 유명한 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<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
7 - 33 전화 채 팅 마니아 (25 분) (지도)7-33 전화 채 팅 마니아 (25 분) 수많은 휴대 전화 사용자 의 통화 기록 을 정 해 통화 횟수 가 가장 많은 채 팅 광 을 찾 아 보 자. 입력 형식: 입력 은 먼저 정수 N (≤ 105) 을 주 고 통화 기...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.