二分圖的判定問題比較少見，簡單來說，就是對于給定的圖，判斷圖是否為二分圖。

可以把每個節點著以黑色和白色之一，使得每條邊的兩個端點顏色不同，不難發現，對于一個當且僅當每個連通分量都是二分圖，因此我們只考慮無向連通圖。

無向圖 G 為二分圖的充分必要條件：G 至少有兩個頂點，且其所有回路的長度均為偶數。

int n;//節點數 vector<int> G[N];//G[i]表示i節點鄰接的點 int color[N];//color[i]=0,1,2 表i節點不涂顏色、涂白色、涂黑色 bool bipartite(int u)//判斷無向圖是否可二分 {for(int i=0;i<G[u].size();i++)//枚舉結點{int v=G[u][i];//相鄰節點if(color[v]==color[u])//若兩結點顏色相同，無法二分return false;if(!color[v])//若結點沒涂顏色{color[v]=3-color[u];//改變結點顏色，使v的顏色與u的顏色對立if(!bipartite(v))//若點v不滿足二分圖話，則無法二分return false;}}return true; }

總結

以上是生活随笔為你收集整理的图论 —— 二分图 —— 二分图判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。