题目链接
思路：将每个学生抽象成点，联系抽象成边，构造无向图，把教室抽象成点要上的颜色，于是这道题就是图染色问题，求图的色数。可以用DFS搜索。
#include <bits/stdc++.h> using namespace std; const int maxn = 110; int G[maxn][maxn],color[maxn],ans=maxn,n; bool judge(int v,int Color) { for(int i=1;i<=n;i++) if(G[v][i]&&color[i]==Color) return false; return true; } void dfs(int v,int cnt) { if(cnt>=ans)//剪枝 return; if(v>n) { ans=min(ans,cnt);//更新答案 return; } for(int i=1;i<=cnt;i++)//遍历当前的所有颜色 { if(judge(v,i))//判断当前点是否能上这个颜色 { color[v]=i; dfs(v+1,cnt); } } //当前点上新的颜色，这种情况也有可能产生最优解 color[v]=cnt+1; dfs(v+1,cnt+1); color[v]=0; } int main() { int k,x,y; cin>>n>>k; for(int i=0;i<k;i++) { cin>>x>>y; G[x][y]=G[y][x]=1; } dfs(1,0); cout<<ans; return 0; }
