蓝桥杯2017年第八届真题-分考场-题解（C++代码）

解题思路：从第一个人开始搜索，遍历已经有的考场，检查在他之前的人中哪一个在这个考场，并且他们认识不认识，如果有认识的就跳过这个考场，去下一个考场，如果没有认识的可以选择放在这个考场，或者最后自己再新开一个考场。

#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e2+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
int n,m;
int g[N][N]; 
int col[N];
int ans=INF;
void dfs(int id,int cnt){//id表示当前是哪个人，cnt表示已经有了几个教室
    if(cnt>=ans)return;
    if(id==n+1){//如果已经搞完所有人
        ans=min(ans,cnt);
        return ;
    }
    for(int i=1;i<=cnt;i++){//遍历每个考场
        bool flag=1;
        for(int j=1;j<id;j++){//遍历他之前的人
            if(col[j]==i&&g[id][j]){//看他之前的人哪个属于当前这个考场i，并且两个认识，就不合法
                flag=0;
                break;
            }
        }
        if(!flag)continue;//不合法就跳过
        col[id]=i;//到这里就这么当前考场是合法的，可以把他试放在这个考场
        dfs(id+1,cnt);
        col[id]=0;
    }
    col[id]=cnt+1;//或者他自己再新开一个考场
    dfs(id+1,cnt+1);
    col[id]=0;
}
int main(){
    cin>>n>>m;
    for(int a,b,i=0;i<m;i++){
        cin>>a>>b;
        g[a][b]=1,g[b][a]=1;//存储认识的人
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}