分考场 【 DFS + 染色问题 】

#include<iostream>
#include<bits/stdc++.h>
#include<string>
using namespace std;
int gra[200][200]; // 记录两个人之间的关系，gra[i][j] == 1 代表 i 和 j 认识
int vis[200][200]; // vis[i][j] == 1 代表第 i 间教室的第 j 人在这间教室。
int n,m;
int c[200]; // c[i] 表示第 i 个房间的人数
int ans; // 最终答案
int flag; // 在 DFS 中用于判断当前 s 是否能分配给当前教室
void dfs(int s, int tot, int num) // s 为当前的人，tot 为当前一共分配的教室，num 为当前分配到了多少人了
{
    if(tot >= ans)
    {
        return ;
    }
    if(num == n)
    {
        ans = min(ans,tot);
        return ;
    }

    for(int i = 1; i <= tot; i ++)
    {
        flag = 1; // 假设能分配
        for(int j = 1; j <= c[i]; j ++)  // c[i] 代表 i教室的总人数
        {
            if(gra[s][vis[i][j]])  // 代表 s 和 vis[i][j] 有关系，也就是第 i 间教室的第 j 同学有关系
            {
                flag = 0;
                break;
            }
        }
        if(flag)
        {
            vis[i][++c[i]] = s;
            dfs(s+1,tot,num+1);
            --c[i];
        }
    }
    vis[tot+1][++c[tot+1]] = s;
    dfs(s+1,tot+1,num+1);
    --c[tot+1];

}
int main()
{
    int u,v;
    scanf("%d\n%d", &n, &m);
    for(int i = 0; i < m; i ++)
    {
        scanf("%d %d", &u, &v);
        gra[u][v] = gra[v][u] = 1;
    }
    ans = n;
    dfs(1,0,0);
    printf("%d\n",ans);
    return 0;
}