蓝桥杯 历届试题 分考场（着色问题、深度优先搜索）-- 酱懵静

历届试题 分考场

问题描述
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

样例输入
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出
5

---

---分割线---

---

注意：如果对图的着色算法不太清楚的同学，建议先去看一下这一篇图的着色算法再来做本题

分析：
很明显，这道题需要用到上一题的算法思想——着色
我们可以把某两个相互认识的同学视为两个相互连接点，那么显然，这两个点不能着相同的颜色（即不能放在同一间教室）。基于这样的一种转换，我们就可以参考上一道题用到的dfs来进行合理的转化，使得其能适用于本题

不过这道题的要求看起来似乎宽松了很多——只需要输出分配教室最少时的数量，而不要你把全部的分配方案都输出（当然，这个数据范围也不可能让你输出：因为本题的数据范围（考试人数，也就是点数）最大是100，要知道在递归树达到50层及更多的时候，栈会爆炸。（你想想递归的过程类似于对n叉树的搜索。假设是二叉树，那么对这100个数据而言就存在50层递归，那当递归到最后一层时，其需要搜索的总次数即为2^50= 1,125,899,906,842,624‬），这个次数已经超出栈的范围了）。实际上也确实难了很多，因为待求的是一个最值，那么这有可能涉及到动态规划，毕竟这道题表面上看来有点像是一个动态规划。
可是这道题的提示已经很明显了，摆明了要用着色算法。

下面说说本题dfs的主要思路，首先传进某个学生，以及一个用于记录当前安排了多少教室的参数room_num，接着通过一个循环，遍历每一间教室，并将每一间教室中的学生与当前传递进来的那个学生进行对比（这里也通过一个循环来实现），一旦遇到了认识的，那么就跳过当前教室，依循环继续去下一间执行同样的操作。如果遍历完所有的教室都是存在认识的，那么就直接给当前这个学生开一间新教室，这时传递的参数是dfs（学生数+1，教室数+1）。
当在上面的循环中，存在某个教室里面的所有人都与传进来的那个人不认识，那么就直接安排当前教室给当前同学。然后继续dfs下一个同学，注意，这时候你传递的参数就应该是dfs（学生数+1，教室数）。

这里有一个陷阱！试想，会不会有一种情况：前面存在某个教室所有人都不认识，于是根据贪心的思想，你应该要把这个人安排到这里以求得最终能得到最小的教室数（注意：上面我的dfs执行的效果也是这样的）。可是实际上，会存在一种可能：即使前面存在某个教室所有人都不认识，你本可以安排当前人在哪里的，但是你如果为他单独再加一间教室或许最终还会获得更小的教室数。

于是，基于上面的这种思想，我们还应该对这个dfs算法进行优化。
而这里的优化，实际上是通过改变程序的执行顺序来实现的，你的目标是需要将上面说到的两个dfs都执行，这样，程序里再写一段取最小值的代码即可。
你要想，你的dfs在执行之后是会回退的，那么为了能够将这两个都能执行到，那么就不能用分支结构。即：不以if-else语句进行分支执行，而是以顺序执行为主，if进行特殊判断作为插入。这样dfs在回退之后，就能继续执行之后的另一个dfs，这也就保证了你的算法能得出最优解。

在涉及到dfs的地方，我们还需要判断一下数据范围。上面也说到了，假设本题给的数据有100个并且存在完全二叉树，那么这里就存在50层递归，那当递归到最后一层时，其需要搜索的总次数即为2^50
这时如果你想要得到满分，那你必须对这个dfs的算法进行剪枝。
剪枝的方案是就是前面提到的多加一个参数room_num，以表示当前安排方案中已经安排的教室的数量。这样当在dfs的过程中找到第一个值之后，那么再往后面的搜索就可以根据这个值进行判断。即如果当前安排的教室数量已经大于了前一次得到的安排教室的数量时，那就直接return，因为这样的前提下安排的教室数不可能会是最小值。表现在代码中就是写一个判断：room_num>ans，作为第一个if语句，如此便能达到剪枝的目的了。

本题中最开始就是没有加那个if语句，因此超时了（仅得了40%的分）。
而加上这代码之后就成功AC了。

---

---分割线---

---

下面直接给出本题完整代码（附有详细注释）：

#include<iostream>
#include<vector>
using namespace std;

const int MAX=105;
bool map[MAX][MAX];			 			//map[x][y]表示x和y认识
int n,m;
int ans=MAX;				 			//最开始必须给ans赋值一个最大值（为最多的人数即可）
vector<int> classroom[MAX];	 			//二维向量classroom[i]=x表示

void dfs(int id,int room_num)			//id表示某个学生的学号，room_num表示当前教室的数量 
{
	if(room_num>=ans) return;			//当现在安排的教室数量已经大于了最小的教室数量的话放弃搜索并回退 
	if(id>n){							//安排的学生数量已经大于所有的学生，就表示已经安排完了所有的学生
		ans=ans<room_num?ans:room_num;
		return;
	}
	for(int i=1;classroom[i].size();i++)//遍历所有教室
	{ 
		int j,len=classroom[i].size();
		for(j=0;j<len;j++)				//检测当前教室是否存在一个人与将要被安排的学生认识 
			if(map[id][classroom[i][j]]) break;
		if(j==len)						//说明当前教室中没有人与当前id的学生认识
		{
			classroom[i].push_back(id);//在当前教室插入此学生 
			dfs(id+1,room_num); 	   //继续安排下一个 
			classroom[i].pop_back();   //回退后需要把这个学生从当前教室清除掉 
		} 
	}
	classroom[room_num+1].push_back(id);//开一间新教室给当前学生 
	dfs(id+1,room_num+1);				//继续安排下一个 
	classroom[room_num+1].pop_back();	//回退后需要把这个学生从当前教室清除掉 
} 

int main()
{
	int x,y;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		map[x][y]=map[y][x]=1;
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}