Bron-Kerbosch算法求最大团

blog

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 44;
bool cn[N][N];
int n,m,x,ans,po[N],cnt[N];
//BK
bool dfs(int x,int cur){
    //cnt[i]表示从i−n这些点的最大团点数
    //po存当前团内的点
    //now表示现在正在搜团内第now个点（注意现在团内只有now−1个点）
    for(int i = x + 1; i <= n; ++i){//[x+1,n]
        if(cur + cnt[i] <= ans) return false;//如果当前团内的点加上要进团的点都不大于ans，直接return
        if(!cn[x][i]) continue;
        int j = 1;
        for(; j < cur; ++j) if(!cn[i][po[j]]) break;
        if(j == cur){//j!=cur那么不能成团
            po[cur] = i;//加入团中
            if(dfs(i,cur + 1)) return true;
        }
    }
    if(cur > ans + 1){//更新
        ans = cur - 1;
        return true;
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i = 1,x,y; i <= m; ++i){
        scanf("%d%d",&x,&y);
        cn[x][y] = cn[y][x] = true;
    }
    for(int i = n; i > 0; --i){
        po[1] = i;
        dfs(i,2);
        cnt[i] = ans;
    }
    printf("%d\n",ans);
    return 0;
}