最大独立集即最大团内点的数量
http://www.cnblogs.com/jianglangcaijin/p/6035945.html付最大独立集和二分图关系
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=200; int g[maxn][maxn]; int bb[maxn],b[maxn]; int t,n,m; int ans,cnt; void dfs(int x) { if(x>n) { if(cnt>ans) { memcpy(b,bb,sizeof(bb)); ans=cnt; } return; } int flag=1; for(int i=1; i<x; i++)//维护最大团 if(bb[i]&&!g[x][i])//这个点不能入最大团 { flag=0; break; } if(flag) { cnt++,bb[x]=1;//把点放入 dfs(x+1); cnt--,bb[x]=0; } if(n-x+cnt>ans)//假设剩余点都是最大团内的点，并且都加进去后可以大于ans dfs(x+1); } void init() { for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { g[i][j]=1; } memset(bb,0,sizeof(bb)); memset(b,0,sizeof(b)); ans=0; cnt=0; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); int x,y; for(int i=1; i<=m; i++) { scanf("%d%d",&x,&y); g[x][y]=0; g[y][x]=0; } dfs(1); printf("%d\n",ans); int first=0; for(int i=1; i<=n; i++) if(b[i]) { if(!first) first=1; else printf(" "); printf("%d",i); } printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7642045.html
