Tô màu đồ thị

Buổi 11 — Brute Force & Sinh tổ hợp Implementation
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
recursion
Submissions
Đề 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$
Draft saved