7201 : 최소 색칠
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
주어진 그래프의 인접한 정점들이 서로 다른 색을 가지도록 칠하려고 합니다. 그래프 정보가 주어질 때, 필요한 최소 색상 수(색수, Chromatic Number)를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. (1 ≤ N ≤ 8, M은 간선 수)
둘째 줄부터 M개의 줄에 간선으로 연결된 두 정점 쌍이 주어집니다.
둘째 줄부터 M개의 줄에 간선으로 연결된 두 정점 쌍이 주어집니다.
출력 설명
필요한 최소 색상 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2
2 3
3 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
삼각형 모양의 완전 그래프(K3)이므로 최소 3가지 색이 필요합니다.