C++回溯法最大团问题

最大团问题是图论中的一个经典问题，指在一个无向图中找到一个完全子图，使得这个子图中的任意两个顶点都有边相连，并且这个子图的顶点数最大。C++回溯法可以用来解决最大团问题。

以下是C++回溯法解决最大团问题的代码实现：

#include <iostream>
using namespace std;

const int MAXN = 100; // 最大顶点数
int n, m, ans; // n为顶点数，m为边数，ans为最大团的大小
int g[MAXN][MAXN]; // 图的邻接矩阵
int vis[MAXN]; // vis[i]表示第i个顶点是否在当前团中

void dfs(int u, int cnt) { // u表示当前搜索的顶点，cnt表示当前团的大小
    if (u > n) { // 搜索完所有顶点
        if (cnt > ans) { // 更新最大团的大小
            ans = cnt;
            for (int i = 1; i <= n; i++) {
                vis[i] = 0;
            }
        }
        return;
    }
    bool flag = true; // 判断当前顶点是否可以加入团中
    for (int i = 1; i < u; i++) {
        if (vis[i] && !g[i][u]) { // 如果i在当前团中，但i和u之间没有边相连
            flag = false;            break;
        }
    }
    if (flag) { // 如果当前顶点可以加入团中
        vis[u] = 1;
        dfs(u + 1, cnt + 1); // 继续搜索下一个顶点
    }
    vis[u] = 0;
    dfs(u + 1, cnt); // 不加入当前顶点，继续搜索下一个顶点
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 1; // 无向图，所以要将边双向连接
    }
    dfs(1, 0); // 从第一个顶点开始搜索
    cout << ans << endl; // 输出最大团的大小
    return 0;
}