You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
const int N = 110;
|
|
|
|
|
int a[N][N]; // 互斥关系
|
|
|
|
|
int res; // 最多时的宝石数量
|
|
|
|
|
int n, m; // n颗宝石,m个互斥关系
|
|
|
|
|
int s[N], sl; // 已经选择了哪些号码的宝石
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// 走到第u号面前
|
|
|
|
|
void dfs(int u) {
|
|
|
|
|
if (u == n + 1) {
|
|
|
|
|
res = max(res, sl);
|
|
|
|
|
return;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// ① 放弃当前宝石
|
|
|
|
|
dfs(u + 1);
|
|
|
|
|
|
|
|
|
|
// ② 选择当前宝石
|
|
|
|
|
int f = 1;
|
|
|
|
|
for (int i = 1; i <= sl; i++) // 遍历每个选择完的号码,利用互斥关系,判断当前枚举的号码u是不是可以加入方案中
|
|
|
|
|
if (a[u][s[i]]) { // 存在互斥号码,不能加入!
|
|
|
|
|
f = 0; // 不能加入标识
|
|
|
|
|
break; // 不用再试了,当前i不行!
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (f) { // 如果没有检查到互斥标识,尝试放入
|
|
|
|
|
s[++sl] = u; // 记录路径中增加了u号宝石
|
|
|
|
|
dfs(u + 1); // 走到下一个宝石面前
|
|
|
|
|
--sl; // 回溯
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
int main() {
|
|
|
|
|
cin >> n >> m;
|
|
|
|
|
while (m--) {
|
|
|
|
|
int x, y;
|
|
|
|
|
cin >> x >> y;
|
|
|
|
|
a[x][y] = a[y][x] = 1; // 记录互斥关系
|
|
|
|
|
}
|
|
|
|
|
// 开始搜索
|
|
|
|
|
dfs(1);
|
|
|
|
|
// 输出结果
|
|
|
|
|
cout << res << endl;
|
|
|
|
|
return 0;
|
|
|
|
|
}
|