題目：http://acm.hdu.edu.cn/showproblem.php?pid=2444

?

題意：給定一個(gè)無(wú)向圖，先判斷它是否是二分圖，如果是則求出最大匹配，否則輸出“No”。

二分圖是這樣一個(gè)圖： 有兩頂點(diǎn)集且圖中每條邊的的兩個(gè)頂點(diǎn)分別位于兩個(gè)頂點(diǎn)集中，每個(gè)頂點(diǎn)集中沒(méi)有邊相連接！

判斷二分圖的常見(jiàn)方法：開(kāi)始對(duì)任意一未染色的頂點(diǎn)染色，之后判斷其相鄰的頂點(diǎn)中，若未染色則將其染上和相鄰頂點(diǎn)不同的顏色， 若已經(jīng)染色且顏色和相鄰頂點(diǎn)的顏色相同則說(shuō)明不是二分圖，若顏色不同則繼續(xù)判斷，用深搜即可。因?yàn)槭菬o(wú)向二分圖的匹配，所以要除以2。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 2005;int head[N],link[N]; bool vis[N],col[N]; int cnt,n,m;struct Edge {int to;int next; };Edge edge[N*N];void Init() {cnt = 0;memset(head,-1,sizeof(head));memset(col,0,sizeof(col)); }void add(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }bool Color(int u) {for(int i=head[u]; ~i; i=edge[i].next){int v = edge[i].to;if(!col[v]){col[v] = !col[u];if(!Color(v)) return false;}else if(col[v] == col[u])return false;}return true; }bool dfs(int u) {for(int i=head[u]; ~i; i=edge[i].next){int v = edge[i].to;if(!vis[v]){vis[v] = 1;if(link[v] == -1 || dfs(link[v])){link[v] = u;return true;}}}return false; }int match() {int ans = 0;memset(link,-1,sizeof(link));for(int i=1; i<=n; i++){memset(vis,0,sizeof(vis));if(dfs(i)) ans++;}return ans; }int main() {while(~scanf("%d%d",&n,&m)){if(n == 1){puts("No");continue;}Init();while(m--){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}col[1] = 1;if(!Color(1)){puts("No");continue;}printf("%d\n",match()>>1);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的二分图判断的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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