性質(zhì) :

• 如果兩個(gè)集合中的點(diǎn)分別染成黑色和白色，可以發(fā)現(xiàn)二分圖中的每一條邊都一定是連接一個(gè)黑色點(diǎn)和一個(gè)白色點(diǎn)。
• 二分圖不存在長(zhǎng)度為奇數(shù)的環(huán)(因?yàn)槊恳粭l邊都是從一個(gè)集合走到另一個(gè)集合，只有走偶數(shù)次才可能回到同一個(gè)集合。)

染色法判定二分圖模板

#include<bits/stdc++.h> using namespace std; const int N=1e5*3+10; int h[N],e[N],ne[N],idx; int st[N],n,m; void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool dfs(int u,int c) {st[u]=c;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]&&!dfs(j,3-c)) return false;else if(st[j]&&st[u]==st[j]) return false;}return true; } int main(void) {memset(h,-1,sizeof h);cin>>n>>m;while(m--){int a,b; cin>>a>>b;add(a,b),add(b,a);}bool flag=1;for(int i=1;i<=n;i++){if(!st[i]&&!dfs(i,1)) flag=0;if(!flag) break;}if(flag) puts("Yes");else puts("No");return 0; }

匈牙利算法解決二分圖的最大匹配模板

const int N=510; const int M=1e5+10; int h[N],e[M],ne[M],idx; int st[N],match[N]; int n1,n2,m; void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++; } bool find(int u) {for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=1;if(match[j]==0|| find(match[j])){match[j]=u;return true;}}}return false; } void init() {int res=0;for(int i=1;i<=n1;i++){memset(st,0,sizeof st);if(find(i)) res++;}cout<<res; }

860. 染色法判定二分圖
861. 二分圖的最大匹配

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

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

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