|
算法思想：
①找增广路
②过奇环中任意一点有增广路，则过奇环亦有增广路，所以可以将奇环缩点
算法流程：
以一个当前未匹配上的点为s点，染为白色，bfs染色，只许白点进队。
当两个白色点有边时，说明遇到奇环，缩点。
当遇到一个未染色且未匹配点时，找到增广路，修改匹配后退出。
代码：
#include<bits/stdc++.h>
#define N 200020
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
queue<int>Q;
int n,m,head[N],pos;
int tot,match[N],fri[N],top[N],ring[N];
bool odd[N],vis[N];
struct edge{int to,next;}e[N<<1];
inline void add(int a,int b)
{
pos++;e[pos].to=b,e[pos].next=head[a],head[a]=pos;
}
inline void insert(int u,int v){add(u,v);add(v,u);}
int fa[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int clo;
inline int lca(int x,int y)
{
clo++;
for(;x;x=find(top[x]))ring[x]=clo;
for(x=y;ring[x]!=clo;x=find(top[x]));
return x;
}
inline void blossom(int x,int y,int p)
{
for(;find(x)!=find(p);x=fri[y])
{
fri[x]=y,y=match[x];
fa[find(x)]=fa[find(y)]=p;
Q.push(y),odd[y]=0;
}
}
inline bool dfs(int s)
{
clo=0;
for(int i=1;i<=n;i++)odd[i]=vis[i]=ring[i]=top[i]=fri[i]=0,fa[i]=i;
while(!Q.empty())Q.pop();vis[s]=1,Q.push(s);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=odd[v]=1,fri[v]=top[v]=u;
if(!match[v])
{
for(int x,y,j=v;j;j=y)
{
x=fri[j],y=match[x];
match[j]=x,match[x]=j;
}return 1;
}
vis[match[v]]=1,top[match[v]]=v,Q.push(match[v]);
}
else if(!odd[v]&&find(v)!=find(u))
{
int p=lca(u,v);
blossom(u,v,p);
blossom(v,u,p);
}
}
}return 0;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
insert(x,y);
}
int ans=0;
for(int i=1;i<=n;i++)if(!match[i])ans+=dfs(i);
printf("%d\n",ans);
for(int i=1;i<=n;i++)printf("%d ",match[i]);
}
| 
转播
