染色法
#include<iostream> #include<algorithm> #include<string.h> #include<map> #include<queue> #include<cmath> #include<cstdio> #include<stack> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=2e5+5; struct node{ int to,next; }edge[maxn]; int cnt=1,head[maxn],n,m; void add(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } int color[maxn]; bool dfs(int u,int c) { color[u]=c; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(!color[v]) { if(!dfs(v,3-c)) return false; } else if(color[u]==color[v]) return false; } return true; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } int flag=1; for(int i=1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1)) { flag=0; break; } } } if(flag) printf("Yes"); else printf("No"); }匈牙利算法
#include<iostream> #include<algorithm> #include<string.h> #include<map> #include<queue> #include<cmath> #include<cstdio> #include<stack> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=1e5+5; struct node{ int to,next; }edge[maxn]; int cnt=1,head[maxn],n,m; void add(int u,int v) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } int book[maxn],match[maxn]; bool find(int x) { for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(!book[v]) { book[v]=1; if(match[v]==0||find(match[v])) { match[v]=x; return true; } } } return false; } int main() { int n1,n2,m; scanf("%d%d%d",&n1,&n2,&m); for(int i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); } int ans=0; for(int i=1;i<=n1;i++) { memset(book,0,sizeof book); if(find(i)) ans++; } printf("%d",ans); return 0; }