蓝桥杯 分考场

蓝桥杯 分考场

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

#include <stdio.h>

int matrix[200][200] = {0};//用邻接矩阵表示图
int cnt[200] = {0};//每个房间里面的人数
int vis[200][200] = {0};//表示第几个房间里第几个人是谁
int res = 1000;//表示最少的房间个数，最开始先赋一个大的数字
int n, m;

void dfs(int x, int num)
{
	int i, j, count;
	
	if (num > res)//如果超出范围就返回
		return;
	
	if (x > num)//当x大于num是，说明所有人都已经排完
	{
		if (res > num)//每次都比较一下，取最少考场的方案
			res = num;
		return;
	}
	
	for (i = 1; i <= num; i++)//遍历每个考场
	{
		count = 0;
		for (j = 1; j <= cnt[i]; j++)//检查当前考场是否所有人都与x不认识
			if (!matrix[x][vis[i][j]])
				count ++;
		
		if (count == cnt[i])//如果都不认识，说明x可以进入该考场
		{
			vis[i][++cnt[i]] = x;//在当前考场添加x
			dfs(x + 1, num);//继续排下一个
			--cnt[i];//回溯
		}
	}

	vis[num + 1][++cnt[num + 1]] = x;//如果遍历所有的考场都不满足x能进入的条件，就添加一间考场
	dfs(x + 1, num + 1);//继续排下一个
	--cnt[num + 1];//回溯
}

int main()
{
    int i;
    int vertex1, vertex2;
    scanf("%d%d", &n, &m);

    for (i = 0; i < m; i++)//构建图
    {
        scanf("%d %d", &vertex1, &vertex2);
        matrix[vertex1][vertex2] = 1;
        matrix[vertex2][vertex1] = 1;
    }

    dfs(1, 0);

    printf("%d\n", res);

    return 0;
}