给定有一个无向图，找出最大团个数。
最大团也就是该图中最大的完全图（各顶点之间都有边）。
算法思想：设p为所有点集的集合，依次取出p中的顶点作为团的起始点，也就是以该点为起点开始拓展，每次查看相邻顶点是否与团内各点联通，若true，则加入该点。
为了进一步降低时间复杂度，采取记忆化递归的方式，从后向前遍历顶点，用cnt数组记录该点以后所成最大团的个数，以此知该点的潜力，达到剪枝的效果。
#include<bits/stdc++.h> using namespace std; #define maxm 55 int g[maxm][maxm];//存图 int vis[maxm];//存放已选择的点 int cnt[maxm];//cnt[i]表示用编号>=i的点能组成的最大团的点数 int ans, n; bool dfs(int cur, int num) {//从第cur个点开始向后添加，当前点是第num个 for (int i = cur + 1; i <= n; i++) { if (cnt[i] + num <= ans)//当前点后的所有点组成的最大团的最大点数+已经加入的点数<=当前最佳答案（最好的情况都不可能超过当前最优解，则进行剪枝） return 0; if (g[cur][i])//两点相邻 { int ok = 1; for (int j = 0; j < num; j++)//是否和当前已经加入团的所有点相邻 if (!g[i][vis[j]]) { ok = 0; break; } if (ok) {//当前点可以加入团中 vis[num] = i; if (dfs(i, num + 1))//第一次dfs成功的一定是最大的 return 1; } } } ans = max(ans, num); return (ans == max(num, ans) ? 0 : 1); } void maxclique() { for (int i = n; i > 0; i--) { vis[0] = i; dfs(i, 1); cnt[i] = ans; } } int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> g[i][j]; g[j][i] = g[i][j]; } maxclique(); cout << cnt[1]; return 0; } /* 5 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 */
