最大獨(dú)立集： 頂點(diǎn)集V中取 K個(gè)頂點(diǎn)，其兩兩間無(wú)連接。

最大團(tuán)：　頂點(diǎn)集V中取 K個(gè)頂點(diǎn)，其兩兩間有邊連接。

最大獨(dú)立集=補(bǔ)圖的最大團(tuán)
最大團(tuán)=補(bǔ)圖的最大獨(dú)立集

#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) // 如果枚舉了所有的節(jié)點(diǎn) {maxx=cnt;memcpy(mark1,mark2,sizeof(mark2)); // 用一個(gè)更大的極大團(tuán)替代原有的極大團(tuán)return;}int flag=true;for(int i=1; i<x; i++) // 檢測(cè)新加入的點(diǎn)是否到團(tuán)中的其他節(jié)點(diǎn)都存在一條邊 {if(mark2[i] && !mp[i][x]){flag=false;break;}}if(flag) // 如果該節(jié)點(diǎn)滿足在這個(gè)團(tuán)中 {mark2[x]=1,cnt++; // 該節(jié)點(diǎn)被加入到完全子圖中去dfs(x+1);mark2[x]=0,cnt--;}if (cnt+n-x>maxx) // 跳過(guò)x節(jié)點(diǎn)進(jìn)行搜索同時(shí)進(jìn)行一個(gè)可行性判定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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Aragaki/p/7554666.html

總結(jié)

以上是生活随笔為你收集整理的poj1419 Graph Coloring 最大独立集(最大团)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。