求最大独立集独立集就是在一个图中选取一些点，这些点互不相邻，这个点集就是独立集最大独立集就是点最多的独立集，很显然，一个图至少一个最大独立集跟图的补图的最大团是一样的图的补图就是把一个图原来的边都删掉，把原来互相之间没有边的点相连最大团就是一个图的最大完全子图完全子图就是一个图的子图是个完全图最大完全子图就是完全子图上的点最多，很显然，一个图至少一个求最大团就是NP完全，我学了一种爆搜大概思路就是维护三个数组a数组存放一个正在考虑的完全子图，b数组存放一个当前最大完全子图，c数组存放第i个点到最后一个点这个区域内所能形成的最大团的点的数量，很显然，c是用来剪枝的从最后一个点依次往前选点作为第一个点丢到a中进行搜索，显然这种作法是为了维护c由于a如果可以扩展，那么肯定是由与a中的点相邻的连点扩展（相邻就是直接与点连接），考虑这些点，如果选出来的点跟a中所有点都相邻，那么这个点丢到a的尾巴，进行下一次搜索，同样为了维护c，当从a中选择一个点作为前驱开始扩展时，我们枚举比这个点下标大的点里是否有它的相邻点，如果有，就开始考虑这些点，若是当前a的数量加上c[i](i为这些点的下标)，还是无法更新当前最大团，那么就不用再考虑这个前驱了，停止关于这个前驱的扩展，为了再快一点，每次搜索如果更新了当前最大团就停止这次搜索，换个起点我们再来，为何这样可以保证正确性，因为毕竟我们枚举了所有起点，考虑到了所有情况，如若不停止，反而会多出一些重复情况。这种爆搜不太好的地方就是必须要用邻接矩阵，很浪费内存，速度的话看RP，，过这个题是没问题的。#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;bool edge[110][110];int n,ans,group[110],box[110],cnt[110];//box存放当前选取的点，group存放当前最大团，cnt存放第i位后可形成的最大团bool dfs(int s,int num){for(int i=s+1;i<=n;i++){if(cnt[i]+num<=ans)return 0;if(edge[s][i]){int j;for(j=0;j<num;j++)if(!edge[i][box[j]])break;if(j==num){box[num]=i;if(dfs(i,num+1))return 1;}}}if(ans<num){ans=num;memcpy(group,box,sizeof(int)*ans);return 1;}return 0;}int main(){int T;cin>>T;while(T–){int m;cin>>n>>m;memset(edge,0,sizeof(edge));while(m–){int from,to;cin>>from>>to;edge[from][to]=edge[to][from]=1;}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)edge[i][j]^=1;ans=1;for(int i=n;i>0;i–){box[0]=i;dfs(i,1);cnt[i]=ans;}cout<<ans<<endl;for(int i=0;i<ans;i++)printf(i==0?"%d":i==ans-1?" %d\n":" %d",group[i]);}}
长江后浪催前浪，一辈新人换旧人。
