最大独立集： 顶点集V中取 K个顶点，其两两间无连接。
最大团： 顶点集V中取 K个顶点，其两两间有边连接。
最大独立集=补图的最大团
最大团=补图的最大独立集
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int mp[110][110],mark1[505],mark2[505]; int n,m; int cnt,maxx; void dfs(int x) { if(x>n) // 如果枚举了所有的节点 { maxx=cnt; memcpy(mark1,mark2,sizeof(mark2)); // 用一个更大的极大团替代原有的极大团 return; } int flag=true; for(int i=1; i<x; i++) // 检测新加入的点是否到团中的其他节点都存在一条边 { if(mark2[i] && !mp[i][x]) { flag=false; break; } } if(flag) // 如果该节点满足在这个团中 { mark2[x]=1,cnt++; // 该节点被加入到完全子图中去 dfs(x+1); mark2[x]=0,cnt--; } if (cnt+n-x>maxx) // 跳过x节点进行搜索同时进行一个可行性判定 dfs(x+1); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(mark1,0,sizeof(mark2)); memset(mark2,0,sizeof(mark2)); maxx=cnt=0; for(int i=0; i<105; i++) fill(mp[i],mp[i]+105,1); for(int i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); mp[a][b]= mp[b][a]=0; } dfs(1); printf("%d ",maxx); int k=0; for(int i=1; i<=n; i++) { if(mark1[i]) { if(k==0) { printf("%d",i); k=1; } else printf(" %d",i); } } puts(""); } return 0; }