首页 > 代码库 > poj1419 Graph Coloring,无向图,最大独立集
poj1419 Graph Coloring,无向图,最大独立集
最大独立集 = 补图的最大团
最小顶点覆盖 + 最大独立集 = V
#include <stdio.h> #include <string.h> const int maxn =100 + 10; int g[maxn][maxn], dp[maxn], n; int x[maxn], ans[maxn], mx; int dfs(int *adj, int ns, int dep) { int t[maxn]; if(0 == ns) { if(dep > mx) { for(int i=0; i<dep; ++i) ans[i] = x[i]; //路径信息 mx = dep; return 1; } return 0; } int i, j, cnt; for(i=0; i < ns; ++i) { int& k = adj[i]; if(dep + n - k <= mx) return 0; if(dep + dp[k] <= mx) return 0; x[dep] = k; //路径信息 for(cnt =0, j = i+1; j < ns; ++j) { int& p = adj[j]; if(g[k][p]) t[cnt++]= p; } if(dfs(t, cnt, dep+1)) return 1; } return 0; } int max_clique(int n) { int i, j, ns; int adj[maxn]; if(n<=0) return 0; mx = 0; for(i = n-1; i >= 0; --i) { x[0] = i; //路径信息 for(ns = 0, j=i+1; j < n; ++j) if(g[i][j]) adj[ns++] = j; dfs(adj, ns, 1); dp[i] = mx; } return mx; } int main() { int t, m, i, j, v, u; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0; i<=n; ++i) for(j=0; j<=n; ++j) g[i][j] = 1; for(i=0; i<m; ++i) { scanf("%d%d",&v,&u); v--;u--; g[v][u] = g[u][v] = 0; } int mmax = max_clique(n); printf("%d\n",mmax); for(i=0; i<mmax; ++i) { printf("%d ",ans[i]+1); } printf("\n"); } return 0; }
poj1419 Graph Coloring,无向图,最大独立集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。