6138 : 그래프 색칠 수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개와 간선 M개로 구성된 그래프가 주어집니다. 인접한 임의의 두 정점의 색이 서로 달라지도록 색칠하고자 합니다.
이 그래프를 완전히 색칠하는 데 필요한 최소의 색상 수(크로마틱 수, Chromatic Number)를 구하는 프로그램을 작성하십시오.
이 그래프를 완전히 색칠하는 데 필요한 최소의 색상 수(크로마틱 수, Chromatic Number)를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 N (1 ≤ N ≤ 20)과 M (0 ≤ M ≤ 100)이 주어집니다.
둘째 줄부터 M개의 줄에 간선 u v가 주어집니다.
둘째 줄부터 M개의 줄에 간선 u v가 주어집니다.
출력 설명
필요한 최소 색상 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2
2 3
3 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
색칠할 수 있는 색의 수 m을 1부터 증가시키며, DFS 백트래킹을 활용해 인접 노드의 색과 겹치지 않게 m-Coloring이 가능한지를 검증하십시오.