分考场—深度优先搜索

解题思路:

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f        //定义一个最大值 
const int max_num=105;
int maze[max_num][max_num];   //全部初始化为0
int ans = inf;                //将最小考场数定义为最大值
int n,m;                      //n个人，m条边
vector<int> q[max_num];       //表示第i个考场有几个人,二维数组，进入和出去比较方便 
//判断考生在某考场是否有认识的人
bool isok(int peo,int kao)
{
	int temp = q[kao].size();    //表示kao个考场有多少人 
	//直接取出来二维数组的数据
	for(int j=0;j<temp;++j){
		if(maze[peo][q[kao][j]])    //找到kao号考场的第j个人的编号
		{
			return false;	
		} 
	} 
	return true;
} 
//深度优先搜索解决分考场问题
void dfs(int peo,int kao)     //表示正在给当前考生编号分考场 
{
	//首先判断边界条件
	if(kao>=ans)  
		return; //还没结束就已经比考场多了,这一步是剪枝 
	if(peo==n+1) {
		//表示当前考生编号超出考生人数--停止
		ans=min(ans,kao);
		return ; 
	}
	//正式开始--判断考生编号peo是否在kao里面有认识的人
	for(int i=0;i<=kao;++i)    //思考一下这个边界条件 
	{
		bool res = isok(peo,i);   //为true说明，没有认识的人 
		if(res==true)
		{
			//将当前人安排在这个考场中
			q[i].push_back(peo);
			//继续深搜
			dfs(peo+1,kao);   //还是目前的考场数
			q[i].pop_back();  //返回重塑 
		}
	}
	//开新考场 
	if(kao+1<=n) 
	{
		q[kao+1].push_back(peo);
		dfs(peo+1,kao+1);   //还是目前的考场数
		q[kao+1].pop_back();  //返回重塑 
	}
} 
int main(){
	//输入考生人数以及之间的关系--邻接矩阵
	cin>>n>>m;
	int t1,t2;
	for(int i=1;i<=m;++i)
	{
		cin>>t1>>t2;
		//人数从0开始计算 
		maze[t1][t2]=1;
		maze[t2][t1]=1;	
	}
	//开始深度优先搜索解题
	//第几个人有几个考场大的问题 
	dfs(1,0);     //第一个人，0个考场
	cout<<ans+1<<endl;   //因为这是一个容器，是从下标0开始的 
	return 0;
}