Coloring Graphs

시간 제한6초메모리 제한1024 MB

요약

정점이 최대 11개인 연결 그래프가 주어질 때, 인접한 두 정점이 같은 색을 쓰지 않도록 하는 최소 색의 수를 구한다.

난이도: 보통10점 중 5점
유형: 백트래킹, 그래프, 완전 탐색
정답자: 아직 제출이 없습니다

문제

To address the impending STEM shortage early on, your local elementary school decided to teach graph theory to its kindergarten students! To tap into their age-specific skills, the students are asked to color the vertices of a graph with colors of their own choosing. There is one constraint, however: they cannot use the same color for two vertices if those vertices are connected by an edge. Furthermore, they are asked to use as few different colors as possible. The illustration shows a few examples of student work.

There is one problem, as you can imagine: there is no money to train teachers to grade these students' submissions! Thus, your task is to write a program that computes the sample solutions for the graphs given on each work sheet!

입력

The input consists of a description of a single graph. The first line contains a number $N$ ( $2 \le N \le 11$ ), the number of vertices in the graph. Vertices are numbered $0 \ldots N-1$ . The following $N$ lines contain one or more numbers each. The $i^{th}$ line contains a list of vertex numbers ${ v\_j }$ , denoting edges from $v\_i$ to each $v\_j$ in the list. You may assume that the graph is connected (there is a path between any two pairs of vertices).

출력

Output the minimum number of colors required to color all vertices of the graph such that no vertices that share an edge are colored using the same color!

The sample input corresponds to the graphs shown on the illustration.

예제5

예제 1
입력
```
4
1 2
0 2 3
0 1
1
```
예상 출력
```
3
```
예제 2
입력
```
5
2 3 4
2 3 4
0 1
0 1
0 1
```
예상 출력
```
2
```
예제 3
입력
```
6
1 3
0 2 4
1 5
0 4
1 3 5
2 4
```
예상 출력
```
2
```
예제 4
입력
```
4
1 2 3
0 2 3
0 1 3
0 1 2
```
예상 출력
```
4
```
예제 5
입력
```
5
1 2
0 2 3
0 1 4
1 4
2 3
```
예상 출력
```
3
```