题目链接: https://www.luogu.org/problem/show?pid=2819 思路： 要求每条边的两个定点着不同颜色，可以按照点来dfs，如果与之相连的点已染上一种颜色，那当前点就不染了
#include<iostream> #include<cstdio> using namespace std; int n,k,m,g[105][105],b[205],ans,x,y; bool check(int x,int y){ for (int i=1;i<=n;i++) if (g[y][i]&&b[i]==x) return 0;//与之相连的点染了颜色 return 1; } void dfs(int x){ if (x>n){//所有点都已染色，方案数+1 ans++;return ; } for (int i=1;i<=m;i++)//m种颜色 if (b[x]==0&&check(i,x)==1){//当前没染色并且与之相连的点没有连第i个颜色 b[x]=i;//当前然i种颜色 dfs(x+1); b[x]=0; } } int main(){ cin>>n>>k>>m; for (int i=1;i<=k;i++){ scanf("%d%d",&x,&y); g[x][y]=1;g[y][x]=1; } dfs(1); cout<<ans; return 0; }