圓桌會議必須滿足：奇數(shù)個人參與，相鄰的不能是敵人（敵人關(guān)系是無向邊）。

求無論如何都不能參加會議的騎士個數(shù)。只需求哪些騎士是可以參加的。

我們求原圖的補圖：只要不是敵人的兩個人就連邊。

在補圖的一個奇圈里（由奇數(shù)個點組成的環(huán)）每個點都是可以參加的。而一個奇圈一定在點雙連通分量里，所以我們把原圖的每個點雙連通分量找出來，然后判斷是否有奇圈。用到了幾個引理：

非二分圖至少有一個奇圈。

點雙連通分量如果有奇圈，那么每個點都在某個奇圈里（不一定是同一個）。

于是問題轉(zhuǎn)化為對每個點雙連通分量，判斷它是不是二分圖，如果不是，那就把它里面所有點都標記為可行，最后用總數(shù)減去可行的就是答案（無論如何都不能參加會議的騎士個數(shù)）。

二分圖染色就是dfs，對一個點染色后，對其相鄰點染上與自己不同的顏色，如果相鄰點已經(jīng)染過，就判斷其顏色是否和自己相同，是則說明不是二分圖，否則跳過該相鄰點。直到全部染完。

#include<cstdio> #include<cstring> const int N = 1010; const int M = 2000010; struct Edge {int to,next; }edge[M]; int head[N],tot; int Low[N],DFN[N],Stack[N],Belong[N]; int Index,top; int block;//點雙連通分量的個數(shù) bool Instack[N]; bool can[N]; bool ok[N];//標記 int tmp[N];//暫時存儲雙連通分量中的點 int cc;//tmp的計數(shù) int color[N];//染色 void addedge(int u,int v) {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } bool dfs(int u,int col)//染色判斷二分圖 {color[u] = col;for(int i = head[u];~i;i = edge[i].next){int v = edge[i].to;if( !ok[v] )continue;if(~color[v]){if(color[v]==col)return false;continue;}if(!dfs(v,!col))return false;}return true; } void Tarjan(int u,int pre) {int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u];~i;i = edge[i].next){v = edge[i].to;if(v == pre)continue;if( !DFN[v] ){Tarjan(v,u);if(Low[u] > Low[v])Low[u] = Low[v];if( Low[v] >= DFN[u]){block++;int vn;cc = 0;memset(ok,false,sizeof ok);do{vn = Stack[--top];Belong[vn] = block;Instack[vn] = false;ok[vn] = true;tmp[cc++] = vn;}while( vn!=v );ok[u] = 1;memset(color,-1,sizeof(color));if( !dfs(u,0) ){can[u] = true;while(cc--)can[tmp[cc]]=true;}}}else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v];} } void solve(int n) {memset(DFN,0,sizeof DFN);memset(Instack,false,sizeof Instack);Index = block = top = 0;memset(can,false,sizeof can);for(int i = 1;i <= n;i++)if(!DFN[i])Tarjan(i,-1);int ans = n;for(int i = 1;i <= n;i++)if(can[i])ans--;printf("%d\n",ans); } void init() {tot = 0;memset(head,-1,sizeof head); } int g[N][N]; int main() {int n,m,u,v;while(scanf("%d%d",&n,&m),n){init();memset(g,0,sizeof g);while(m--){scanf("%d%d",&u,&v);g[u][v]=g[v][u]=1;}for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)if(i != j && g[i][j]==0)addedge(i,j);solve(n);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【POJ 2942】Knights of the Round Table（点双连通分量，二分图染色）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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