#include<iostream> using namespace std; int k, v, m; //v 顶点 k 边数 m 颜色种类 int ans; //记录最后答案 int col[1010]; //标记每个顶点所图颜色 int graph[1010][1010]; //二维数组存图 bool judge(int p, int color) //判断p点是否能图该颜色 { int i, flag = 1; // 遍历与p点相邻接的点，如果p点所图颜色与这些点相同，那么p点就不能图这个颜色 for (i = 1; i <= v; i++) { if (graph[p][i] == 1 && color == col[i]) return false; } return true; } void dfs(int vec) //深搜，可理解为给vec这点图颜色 { //如果当前所图的点的编号大于总共给的点的个数，那么说明此种图色方法可行 if (vec > v) { ans++; return; } int i; //遍历所有颜色，并判断是否能图这种颜色 for (i = 1; i <= m; i++) { if (judge(vec, i)) { col[vec] = i; dfs(vec + 1); col[vec] = 0; //回溯 } } } int main() { cin >> v >> k >> m; int i; for (i = 1; i <= k; i++) { int x, y; cin >> x >> y; graph[x][y] = 1; //注意是无向图 graph[y][x] = 1; } dfs(1); //从顶点1开始图色 cout << ans << endl; return 0; }