Tô màu đồ thị
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
recursion
Đề bài
Cho đồ thị vô hướng $N$ đỉnh và $M$ cạnh. Hãy đếm số cách tô $N$ đỉnh bằng $K$ màu (đánh số $1$ đến $K$) sao cho hai đỉnh kề nhau không cùng màu.
Dữ liệu vào
- Dòng đầu: ba số nguyên $N$, $M$, $K$ $(1 \le N \le 10, 0 \le M \le N(N-1)/2, 1 \le K \le 5)$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số $u, v$ $(1 \le u < v \le N)$ mô tả cạnh.
Dữ liệu ra
- Một số nguyên — số cách tô màu hợp lệ.
Ví dụ
| Input | Output |
|---|---|
| 3 3 3\n1 2\n2 3\n1 3 | 6 |
| 3 2 2\n1 2\n2 3 | 2 |
Giới hạn
- $1 \le N \le 10$
- $0 \le M \le N(N-1)/2$
- $1 \le K \le 5$
Community Discussion