Bron-Kerbosch 算法计算图的最大全连通分量(团clique)
最大独立集： 顶点集V中取 K个顶点，其两两间无连接。
最大团： 顶点集V中取 K个顶点，其两两间有边连接。
最大团中顶点数量 = 补图的最大独立集中顶点数量
就可以通过求其补图中最大团中顶点数量,就可得出原图中最大独立集中顶点数量了.
对于求解 最大团中顶点数量 的搜索过程中用到的剪枝,如下
1. 剪枝1：常用的指定顺序, 即枚举第i个顶后, 以后再枚举时只考虑下标比大它的, 避免重复。
2. 剪枝2：自己开始从前往后的枚举顶点, TLE两次. 后来从后往前枚举顶点，发现可以利用顶点之间的承袭性.我用num[i] 记录的可选顶点集合为 V[i, i+1, ... , n] 中的最大团数目， 目标是求num[1].
分析易知, num[i] = num[i+1] 或者 num[i]+1 (num[1...n] 具有非降的单调性,从后往前求)
由这个式子以及num[]信息的记录，使得我们可以增加两处剪枝:
3.上/下剪枝：假设当前枚举的是顶点x, 它的第一个邻接顶是i (标号一定比x大，即num[i]已经求出) 我们可以知道， 若 1 + num[i] <= best, 那么是没必要往下枚举这个顶点x了，因为包含它的团是不可能超过我们目前的最优值的。
4. 立即返回剪枝: 由于num[i]最大可能为num[i+1]+1, 所以在枚举顶点i时，只要一更新best，可知此时的num[i]就为num[i+1]+1了，不需要再去尝试找其他的方案了，所以应立即返回.
2. 剪枝2：自己开始从前往后的枚举顶点, TLE两次. 后来从后往前枚举顶点，发现可以利用顶点之间的承袭性.我用num[i] 记录的可选顶点集合为 V[i, i+1, ... , n] 中的最大团数目， 目标是求num[1].
分析易知, num[i] = num[i+1] 或者 num[i]+1 (num[1...n] 具有非降的单调性,从后往前求)
由这个式子以及num[]信息的记录，使得我们可以增加两处剪枝:
3.上/下剪枝：假设当前枚举的是顶点x, 它的第一个邻接顶是i (标号一定比x大，即num[i]已经求出) 我们可以知道， 若 1 + num[i] <= best, 那么是没必要往下枚举这个顶点x了，因为包含它的团是不可能超过我们目前的最优值的。
4. 立即返回剪枝: 由于num[i]最大可能为num[i+1]+1, 所以在枚举顶点i时，只要一更新best，可知此时的num[i]就为num[i+1]+1了，不需要再去尝试找其他的方案了，所以应立即返回.
#include<cstdio>
#include<cstdlib>
#include<cstring>int best;
int num[maxn];
// int x[maxn];
int path[maxn];
int g[maxn][maxn], n;bool dfs( int *adj, int total, int cnt ){ // total: 与u相连的顶点数量 , cnt表示当前团的数量 int i, j, k;int t[maxn];if( total == 0 ){ // 当此团中最后一个点 没有 比起序号大 的顶点相连时 if( best < cnt ){ // 问题1：best为最大团中顶点的数量 // for( i = 0; i < cnt; i++) path[i] = x[i];best = cnt; return true; } return false;} for( i = 0; i < totl; i++){ // 枚举每一个与 u 相连的顶点 adj[i] if( cnt+(total-i) <= best ) return false; // 剪枝1， 若当前 顶点数量cnt 加上还能够增加的最大数量 仍小于 best则 退出并返回false if( cnt+num[adj[i]] <= best ) return false; // 剪枝2， 若当前 顶点数量cnt 加上 包含adj[i]的最大团顶点数 仍小于 best则 退出并返回false // x[cnt] = adj[i];for( k = 0, j = i+1, j < total; j++ ) // 扫描 与u相连的顶点 中与 adj[u]相连的顶点 并存储到 数组 t[]中，数量为k if( g[ adj[i] ][ adj[j] ] )t[ k++ ] = adj[j];if( dfs( t, k, cnt+1 ) ) return true;} return false;
}
int MaximumClique(){int i, j, k;int adj[maxn];if( n <= 0 ) return 0;best = 0;for( i = n-1; i >= 0; i-- ){// x[0] = i; for( k = 0, j = i+1, j < n; j++ ) // 遍历 [i+1, n] 间顶点， if( g[i][j] ) adj[k++] = j;dfs( adj, k, 1 ); // *adj, total, cntnum[i] = best; // 得出顶点 i, 出发构成最大团 中顶点数量 } return best;
}