最大团+极大团计数(HDOJ 1530+POJ 2989, Bron-Kerbosch )

极大团：无法从图中再加入一个顶点使得此顶点集的顶点两两相连的顶点集

因此单个顶点也可能是一个极大团

最大团：一个包含顶点数最多的极大团

最大独立集=补图的最大团

定理：最大独立集=补图的最大团，最大团=补图的最大独立集

Bron-kerbosch模板

说明

all-已取顶点集，some-未处理顶点集(初始状态是全部顶点)，none-不取的顶点集，g-边，
S-极大团数量，ans-最大团结点数；
结点编号1~n，0用于辅助，表示被删除；
求最大团顶点数时只要some；要求记录路径时要all；
求极大团数量要some、none；要求记录路径时要all；

极大团计数

输入：some，g；
输出：S；
调用方法：dfs(0,0,n,0);
some的初始化:for(int I=0; I<n; ++I) some[0][I]=I+1;
复杂度爆炸，可处理一两百个点

POJ 2989 All friends

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 129;

int n, m;
int S;
int some[N][N], all[N][N], none[N][N], g[N][N];
void dfs(int d, int an, int sn, int nn) {
    if(!sn&&!nn) ++S;
    if(S>1000) return; //题意表明S超过1000就输出Impossible
    int u=some[d][0];
    for(int i=0; i<sn; ++i) {
        int v=some[d][i];
        if(g[u][v]) continue;
        int tsn=0, tnn=0;
        //for(int j=0; j<an; ++j) all[d+1][j]=all[d][j];
        //all[d+1][an]=v;  //可以不写这两行
        for(int j=0; j<sn; ++j) if(g[v][some[d][j]])
            some[d+1][tsn++]=some[d][j];
        for(int j=0; j<nn; ++j) if(g[v][none[d][j]])
            none[d+1][tnn++]=none[d][j];
        dfs(d+1,an+1,tsn,tnn);
        some[d][i]=0, none[d][nn++]=v;
    }
}

int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m) {
        S=0;
        memset(g,0,sizeof(g));
        for(int i=0; i<m; ++i) {
            int a, b;
            cin>>a>>b;
            g[a][b]=g[b][a]=1;
        }
        for(int i=0; i<n; ++i) some[0][i]=i+1; //some的初始化
        dfs(0,0,n,0);
        if(S>1000) cout<<"Too many maximal sets of friends."<<endl;
        else cout<<S<<endl;
    }
}

最大团

输入：some，g；
输出：ans，最大团顶点集保存在all[ans]数组的前ans个数，即all[ans][i]；
调用方式：dfs(0,n,0);
复杂度依然爆炸，可处理一两百个点

POJ 2989 All friends

#include "bits/stdc++.h"

using namespace std;

const int N = 51;

int n, ans;
int some[N][N], g[N][N];
void dfs(int d, int sn, int an) {
    if(sn+an<=ans) return;
    if(!sn) {
        ans=max(ans,an);
        return;
    }
    int u=some[d][0];
    for(int i=0; i<sn; ++i) {
        int v=some[d][i];
        if(g[u][v]) continue;
        int tsn=0;
        //for(int j=0; j<an; ++j) all[d+1][j]=all[d][j];
        //all[d+1][an]=v;  //这两行代码可以保存最大团顶点集
        for(int j=0; j<sn; ++j) if(g[v][some[d][j]])
            some[d+1][tsn++]=some[d][j];
        dfs(d+1,tsn,an+1);
        some[d][i]=0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    while(cin>>n, n) {
        ans=0;
        memset(g,0,sizeof(g));
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j) cin>>g[i][j];
        for(int i=0; i<n; ++i) some[0][i]=i+1;
        dfs(0,n,0);
        cout<<ans<<endl;
    }
}