POJ 1419 最大独立集

POJ 1419 最大独立集

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

这种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( "%dn",ans );printf( "%d",f[0] );for( int i=1;i<len;i++ )printf( " %d",f[i] );printf( "n" );}return 0;
}