【问题描述】给定无向连通图G和m种不同的颜色,用这些颜色给图的各个顶点着一种颜色,若某种方案使得图中每条边的2个顶点的颜色都不相同,则是一个有效方案。请使用回溯法编程找出所有的有效方案。
【输入形式】输入的第一行有3个正整数n,m和k,分别表示图G中有n个顶点,m条边,k种颜色。接下来m行,每行中有2个整数i,j,表示节点i和节点j之间存在一条边(节点编号从1开始)。
【输出形式】输出1行包含1个正整数,表示所有的着色方案数。
【样例输入】
5 7 3
1 2
1 3
2 4
2 5
3 4
3 5
4 5
【样例输出】
12
#include<bits/stdc++.h>
using namespace std;
int n , m, k;
const int N = 1e5+10;
int h[N],e[N],ne[N],idx;
int color[N];//color[i] 表示第i个点的颜色
int ans;
void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//判断点u能否染上颜色co
bool check(int u,int co)
{
//检查相邻点的颜色
for(int i = h[u] ; i != -1; i = ne[i])
{
int j = e[i];
if(color[j] == co)return false;
}
color[u] = co;
return true;
}
void dfs(int x)
{
//递归出口
if(x == n + 1)
{
ans++;
return;
}
//依次遍历颜色,染上合适的颜色
for(int i = 1 ;i <= k ; i ++)
{
if(check(x,i))
{
dfs(x+1);
}
color[x] = 0;
}
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m>>k;
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);//无向图
}
dfs(1);
cout<<ans;
return 0;
}