[蓝桥杯] 分考场

分考场

题目

n个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求是少需要分几个考场才能满足条件。

输入格式

第一行，一个整数n(1<n<100)，表示参加考试的人数。

第二行，一个整数m，表示接下来有m行数据

以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

一行一个整数，表示最少分几个考场。

输入样例

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

输出样例

5

题解

思路

• DFS 深搜剪枝

相似题

• 小猫爬山

#include <iostream>

using namespace std;

const int N = 105, MAX = 0x3f3f3f3f;
int g[N][N], r[N], f[N][N], n, m, ans = MAX;
bool st[N];

void dfs(int u, int k) {
	if (ans <= k) return;
	if (u == n + 1) {
		ans = k; 
		return;
	}
	
	for (int i = 1; i <= k; i ++) {
		bool flag = false;
		for (int j = 1; j <= r[i]; j ++) {
			if (g[u][f[i][j]]) {
				flag = true;
				break;
			}			
		}
		
		if (!flag) {
			f[i][++r[i]] = u;
			dfs(u + 1, k);
			-- r[i];
		}
	}
	
	f[k+1][++ r[k+1]] = u;
	dfs(u + 1, k + 1);
	-- r[k+1];
}

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