学步园

查了很多资料，看了很多课件..

这种NP难问题.. 确实什么轻易的解法... 长路漫漫。

直接求最大独立集的方法能写了，最大团怎么求呢？

另外吐槽一句：网上很多题解中都有最大独立集=补图的最大团。这没错。

但是，很多都有一句下面是求最大团的代码.. 我去.. 概念清楚了再来写题解好么.. 吐槽完毕.

#include<iostream>
using namespace std;

int N,M;
struct Edge
{
 	   int v,next;
}E[111111];

int ptr[111],ans,Edgenum,set[111],f[111];
int len;

void addEdge( int u,int v )
{
 	 E[Edgenum].v=v;
 	 E[Edgenum].next=ptr[u];
 	 ptr[u]=Edgenum++;
}

void dfs( int cur ,int num )
{
 	 if( cur>N )
 	 {
	  	 if( num>ans )
	  	 {
		  	 ans=num;
		  	 len=0;
		  	 for( int i=1;i<=N;i++ )
		  	 	  if( set[i] )
		  	 	  	  f[len++]=i;
	  	 }
	  	 return ;
	 }
	 bool flag=1;
	 for( int i=ptr[cur];i!=-1;i=E[i].next )
	 {
	  	  if( set[E[i].v] )
	  	  {
		   	  flag=0;
		   	  break;
  		  }
  	 }
  	 if( flag )
  	 {
	  	 set[cur]=1;
	  	 dfs(cur+1,num+1);
	  	 set[cur]=0;
  	 }
  	 if( num+(N-cur)>ans )
  	 	 dfs( cur+1,num );
}

int main()
{
 	int T;
 	scanf( "%d",&T );
 	while( T-- )
 	{
	 	   memset( ptr,-1,sizeof(ptr) );
	 	   memset( set,0,sizeof(set) );
	 	   ans=0;Edgenum=0;
	 	   scanf( "%d %d",&N,&M );
	 	   for( int i=0;i<M;i++ )
	 	   {
		   		int u,v;
		   		scanf( "%d %d",&u,&v );
		   		addEdge( u,v );
		   		addEdge( v,u );
		   }
		   dfs(1,0);
		   printf( "%d\n",ans );
		   printf( "%d",f[0] );
		   for( int i=1;i<len;i++ )
		   		printf( " %d",f[i] );
		   printf( "\n" );
  	}
 	return 0;
}