一般图最大团

讲解：（转载于https://blog.csdn.net/SparkFucker/article/details/83051133）

Bron-Kerbosch算法

该算法本质也是DFS。引入三个集合，all集合，some集合，none集合，其中some集合代表待检查且可能能加入团的节点，none集合代表已经检查过且我们认为不能加入团的节点，all则是检查过并且我们认为能加入最大团的节点，当some集合和none集合都为空的时候，all集合即为我们需要求的极大团。每次我们检查some集合里的一个节点，并把它加入all集合，那么可能加入待检查序列的就是它自己的邻接点（毕竟要保证团内所有点都有边相连），和some集合做一个交集，none集合同样和邻接点们作交集，以保证some和none里面的点和all里的点都有边相连。把当前检查点从all里拿出来以后就放入none里面，再从some集合的下一个开始检查。some集合为空的时候就没有可以加入all集合的点了，some集合为空且none集合不为空的时候就代表none集合里面的点放进all集合团会更大（之前检查过这种情况），所以一定要两个集合都为空才行。

这里还要介绍一种优化方法，因为不加这个优化可能连板子题都会TLE。如果我们要从some里选一个点pivot加入到all里的话，它的邻接点势必会因为和some作交集而留在some里待检查，在下一层DFS里势必会被检查，所以没有必要在检查pivot的这一层里再以它们为起点去检查，这会导致重复。选pivot的时候也可以以度数的大小选度数最大的点，这样能减少的检查次数也最多。

//一般图的最大独立集=一般图补图的最大团 
#include<cstdio>
#include<cstring>

一般图最大团

讲解：（转载于https://blog.csdn.net/SparkFucker/article/details/83051133 ）

Bron-Kerbosch算法

该算法本质也是DFS。引入三个集合，all集合，some集合，none集合，其中some集合代表待检查且可能能加入团的节点，none集合代表已经检查过且我们认为不能加入团的节点，all则是检查过并且我们认为能加入最大团的节点，当some集合和none集合都为空的时候，all集合即为我们需要求的极大团。每次我们检查some集合里的一个节点，并把它加入all集合，那么可能加入待检查序列的就是它自己的邻接点（毕竟要保证团内所有点都有边相连），和some集合做一个交集，none集合同样和邻接点们作交集，以保证some和none里面的点和all里的点都有边相连。把当前检查点从all里拿出来以后就放入none里面，再从some集合的下一个开始检查。some集合为空的时候就没有可以加入all集合的点了，some集合为空且none集合不为空的时候就代表none集合里面的点放进all集合团会更大（之前检查过这种情况），所以一定要两个集合都为空才行。

这里还要介绍一种优化方法，因为不加这个优化可能连板子题都会TLE。如果我们要从some里选一个点pivot加入到all里的话，它的邻接点势必会因为和some作交集而留在some里待检查，在下一层DFS里势必会被检查，所以没有必要在检查pivot的这一层里再以它们为起点去检查，这会导致重复。选pivot的时候也可以以度数的大小选度数最大的点，这样能减少的检查次数也最多。
---------------------
作者：SparkFucker
来源：CSDN
原文：https://blog.csdn.net/SparkFucker/article/details/83051133
版权声明：本文为博主原创文章，转载请附上博文链接！

代码（码风很丑）：

//一般图的最大独立集=一般图补图的最大团 
#include<cstdio>
#include<cstring>
#include<algorithm>
using  namespace  std;
inline  void  getx(int  &x)
{
 x=0;char  c=getchar();
 while(c>'9'  ||  c<'0')c=getchar();
 while(c<='9'  &&  c>='0')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
bool  ma[410][410];/*反向建图，True没边，False有边*/
int  some[410][410]/*可能成为下一个在团中的点*/,none[410][410]/*已经找过的且与目前团中所有点有边的点*/,all[410][410]/*团中点，目前没用*/;
int  n,m,ans;
int  deg[410];//每个点的在反图的度数 
inline  bool  cmp(int  x,int  y){return  deg[x]>deg[y];}//度数排序 
void  BK(int  pos,int  al,int  so,int  no)
{
 if(al+so<=ans)return  ;//剪枝优化 
 if(so==0  &&  no==0/*判重*/)
 {
  ans=al;
  return  ;
 }
 int  pi=0;//优化 
 if(so)//all可继承上一层 
 {
  pi=some[pos][1];//因为已经按度数排序了 
  for(int  i=1;i<=al;i++)all[pos+1][i]=all[pos][i];
 }
 for(int  i=1;i<=so;i++)
 {
  int  nxt=some[pos][i];//目前放进团中的点 
  if(!ma[pi][nxt])continue;//优化 
  int  nno=0,nso=0;//下一层的some和none 
  for(int  j=1;j<=so;j++)//在some找与这个点有边相连的点 
  {
   if(!ma[nxt][some[pos][j]])some[pos+1][++nso]=some[pos][j];
  }
  for(int  j=1;j<=no;j++)//在none找与这个点有边相连的点 
  {
   if(!ma[nxt][none[pos][j]])none[pos+1][++nno]=none[pos][j];
  }
  all[pos+1][al+1]=nxt;
  BK(pos+1,al+1,nso,nno);
  some[pos][i]=0;none[pos][++no]=nxt;//把这个点踢到none里面 
 }
}
int  main()
{
 getx(n);getx(m);
 for(int  i=1;i<=n;i++)some[0][i]=i,deg[i]=n-1,ma[i][i]=ma[0][i]=ma[i][0]=True;//初始化 
 for(int  i=1;i<=m;i++)
 {
  int  x,y;getx(x);getx(y);//快读 
  ma[x][y]=ma[y][x]=True;deg[x]--;deg[y]--;
 }
 sort(some[0]+1,some[0]+n+1,cmp);
 ans=0;BK(0,0,n,0);
 printf("%d\n",ans);
 return  0;
}