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.

47 lines
1.3 KiB

2 years ago
#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;
}