python/TangDou/LanQiaoBei/LanQiao14STEMA202303/4.cpp

#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;
}