当且仅当图中不含奇数环
由于图中没有奇数环,所以染色过程没有矛盾
染色法
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=100010,M=200010; int n,m; int h[N],ne[M],e[M],idx=0;//注意因为是无向图,边数开两倍 int colour[N]; void add(int a,int b) { ne[idx]=h[a];e[idx]=b;h[a]=idx++; } bool dfs(int u,int k) { colour[u]=k;//给第一个染色 for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i];//然后读取下一个元素,没染色进行递归染色,递归同时进行判断,如果染色冲突,返回false if(!colour[j]){ if(!dfs(j,3-k)) return false; } else if(colour[j]==k)//染色冲突 return false; } return true; } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); while(m--) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } bool flag=true; for(int i=1;i<=n;i++)//按个判断染色 { if(!colour[i]) if(!dfs(i,1)) { flag=false; break; } } if(flag) puts("Yes"); else puts("No"); return 0; }
匈牙利算法
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int n1,n2,m; const int N=510,M=100010; int h[N],ne[M],e[M],idx=0; int match[N];//匹配,每个女生对应的男生 bool st[N];//判重,不要每次搜一个点,为了占位,让 if(match[j]==0||find(match[j])) 再重找时不遍历该点 void add(int a,int b) { ne[idx]=h[a];e[idx]=b;h[a]=idx++; } bool find(int x) { for(int i=h[x];i!=-1;i=ne[i])//遍历男生所有的女生 { int j=e[i]; if(!st[j])//没遍历过 { st[j]=true;//加上 if(match[j]==0||find(match[j]))//没匹配和等待备胎 { match[j]=x; return true; } } } return false; } int main() { scanf("%d%d%d",&n1,&n2,&m); memset(h,-1,sizeof h); while(m--) { int x,y; scanf("%d%d",&x,&y); add(x,y); } int res=0; for(int i=1;i<=n1;i++) { memset(st,false,sizeof st);//没次重新遍历前必须初始化 if(find(i)) res++; } printf("%d\n",res); return 0; }