分考场

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　n个人参加某项特殊考试。
　　为了公平，要求任何两个认识的人不能分在同一个考场。
　　求是少需要分几个考场才能满足条件。
输入格式
　　第一行，一个整数n(1<n<100)，表示参加考试的人数。
　　第二行，一个整数m，表示接下来有m行数据
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
　　一行一个整数，表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4

方法

开始以为是最大连通分量个数wa了一发，后来有因为暴力缺少剪枝wa了n发。。。就是暴力从第一个人看到第n个人，看能不能放在前c个考场里。

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int n, m;

int clas[N][N];
bool g[N][N];
int res = 0x3f3f3f3f;

void dfs(int u, int c){
    
    if(c >= res) return; // 如果当前分配的考场数已经比最小情况大，就不需要再做了
    
    if(u == n + 1){
        res = min(res, c);
        return;
    }
    
    for(int i = 1; i <= c; i ++){
        int j = 0;
        while(clas[i][j] && !g[u][clas[i][j]]) j ++;
        
        if(clas[i][j] == 0){
            clas[i][j] = u;
            dfs(u + 1, c);
            clas[i][j] = 0;
        }
    }
    
    clas[c + 1][0] = u; 
    dfs(u + 1, c + 1);
    clas[c + 1][0] = 0;
}

int main(){
    cin >> n >> m;
    
    while(m --){
        int a, b;
        cin >> a >> b;
        
        g[a][b] = g[b][a] = 1;
    }
    
    dfs(1, 1);
    
    cout << res << endl;
    
    return 0;
}

分考场

原文：https://www.cnblogs.com/tomori/p/13476482.html