poj1419 Graph Coloring 最大独立集(最大团)

最大独立集： 顶点集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\n",maxx);int k=0;for(int i=1; i<=n; i++){if(mark1[i]){if(k==0){printf("%d",i);k=1;}elseprintf(" %d",i);}}puts("");}return 0; }

 

转载于:https://www.cnblogs.com/Aragaki/p/7554666.html

总结

以上是生活随笔为你收集整理的poj1419 Graph Coloring 最大独立集(最大团)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。