R := {}
P := node set of G
X := {}
BronKerbosch1(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}
BronKerbosch(All, Some, None):
if Some and None are both empty:
report All as a maximal clique // 所有点已选完,且没有不能选的点,累加答案
for each vertex v in Some: // 枚举 Some 中的每一个元素
BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))
// 将 v 加入 All,显然只有与 v 为朋友的人才能作为备选,None 中也只有与 v 为朋友的才会对接下来造成影响
Some := Some - {v} // 已经搜过,从 Some 中删除,加入 None
None := None ⋃ {v}
#include<cstring>#include<iostream>usingnamespacestd;constintmaxn=130;boolmp[maxn][maxn];intsome[maxn][maxn],none[maxn][maxn],all[maxn][maxn];intn,m,ans;voiddfs(intd,intan,intsn,intnn){if(!sn&&!nn)++ans;intu=some[d][0];for(inti=0;i<sn;++i){intv=some[d][i];if(mp[u][v])continue;for(intj=0;j<an;++j)all[d+1][j]=all[d][j];all[d+1][an]=v;inttsn=0,tnn=0;for(intj=0;j<sn;++j)if(mp[v][some[d][j]])some[d+1][tsn++]=some[d][j];for(intj=0;j<nn;++j)if(mp[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;if(ans>1000)return;}}intwork(){ans=0;for(inti=0;i<n;++i)some[1][i]=i+1;dfs(1,0,n,0);returnans;}intmain(){cin.tie(nullptr)->sync_with_stdio(false);while(cin>>n>>m){memset(mp,0,sizeofmp);for(inti=1;i<=m;++i){intu,v;cin>>u>>v;mp[u][v]=mp[v][u]=1;}inttmp=work();if(tmp>1000)cout<<"Too many maximal sets of friends.\n";elsecout<<tmp<<'\n';}return0;}