题解 P6113 【【模板】一般图最大匹配】

upd：修改了几处语病。

【模板】带花树算法

能使用匈牙利算法做出这道题会对理解本文有帮助。

定义图的一组匹配为图的一个边集，保证边集中的边两两没有公共定点。

定义一条边是匹配边当且仅当这条边属于一个匹配，一个点被匹配当且仅当这个点是一条匹配边的端点。

寻找图上的最大匹配常常使用增广路算法。在这里，一条增广路定义为一条起点和终点不相同且均未被匹配的路径，保证路径上的边是非匹配边和匹配边交替。

可以发现，增广路一定包含奇数条边，且将这些边依次翻转（即匹配边变成非匹配边，非匹配边变成匹配边）后得到的还是一组匹配。

这样，每找到一条增广路，就可以使得图中的匹配数量 +1。因此，一个匹配是最大匹配当且仅当图中不存在增广路。

对于二分图，可以使用匈牙利算法可以在 O(nm) 的时间内求出最大匹配。

匈牙利算法寻找的增广路实际上是一条有向的增广路，其中的匹配边的方向是唯一的。这在二分图中是正确的，但是在一般图中，匹配边在增广路中的方向不是唯一的，这使得匈牙利算法中一个点不能被访问两次的限制错误。因此一般图的最大匹配不能用匈牙利算法求解。

一般图和二分图的区别只有奇环的有无，对于一个大小为 2k+1 的奇环，最多只有 k 对匹配，因此一定有至少一个节点能够向外匹配。同时，通过环内增广，每个节点都可以成为这个向外匹配的点。

因此，在求匹配的时候，一个奇环和一个节点是等价的，所以可以将奇环缩成点后当成二分图进行匹配。

将奇环缩成的节点叫做花，对原图用 bfs 找一条增广路，这棵节点可能是花的 bfs 树就称作带花树。

在带花树上 bfs，并尝试对访问到的节点进行黑白染色。假设起点是黑点，那么黑->白的边是非匹配边，白->黑的边是匹配边。遍历黑点的出边，如果访问到的点未被染色且未被匹配，那么就找到了一条增广路。如果被匹配了，则将该点染白色，将该点的匹配点染黑色并加入队列中。

如果访问到的点是白点，那么找到了一个偶环，没有影响无需处理。如果访问到的点是黑点，那么找到了一个奇环，在 bfs 树上找到这两个点的 lca 即可定位这个奇环，可以用并查集将其缩起来。因为缩起来的环是一个黑点，所以环上的白点都需改成黑点并加入到队列中。

为了方便地遍历这条增广路，对每个点存一个前驱 pre 表示这个点出发走一条非匹配边后应该到达哪个节点。被缩掉的环上的非匹配边的 pre 应该都是双向的，在缩环时处理一下。

可以发现，通过缩环减少一个点的复杂度为均摊 O(logn)，因为使用了并查集。找到一条增广路最坏情况下需要遍历整张图，复杂度为 O(n+m)。

因此，用带花树算法求出一般图最大匹配的复杂度为 O(n(nlogn+m))，通常可以当做 O(nm)（和匈牙利一样跑不满就是了）。

题外话，额外存一下每个花在树上的节点是哪一个就可以按秩合并了。

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u) for(int i=h[u],v;v=e[i].t,i;i=e[i].n)
const int N=1e3+1,M=1e5+1;
queue<int>q;
int n,m,tot,qwq,ans;
int h[N],lk[N],tag[N],fa[N],pre[N],dfn[N];
struct edge{int t,n;}e[M];
V link(int x,int y){lk[x]=y,lk[y]=x;}
V add_edge(int x,int y){
    if(!lk[x]&&!lk[y])link(x,y),ans++;
    e[++tot]=(edge){y,h[x]},h[x]=tot;
    e[++tot]=(edge){x,h[y]},h[y]=tot;
}
V rev(int x){if(x)rev(x[pre][lk]),link(x,pre[x]);}
I find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
I lca(int x,int y){
    for(qwq++;;x=x[lk][pre],swap(x,y))
        if(dfn[x=find(x)]==qwq)return x;
        else if(x)dfn[x]=qwq;
}
V shrink(int x,int y,int p){
    for(;find(x)!=p;x=pre[y]){
        pre[x]=y,y=lk[x],fa[x]=fa[y]=p;
        if(tag[y]==2)tag[y]=1,q.push(y);
    }
}
I blossom(int u){
    FOR(i,1,n)tag[i]=pre[i]=0,fa[i]=i;
    tag[u]=1,q=queue<int>(),q.push(u);
    for(int p;!q.empty();q.pop())REP(u=q.front())
        if(tag[v]==1)
            p=lca(u,v),shrink(u,v,p),shrink(v,u,p);
        else if(!tag[v]){
            pre[v]=u,tag[v]=2;
            if(!lk[v])return rev(v),1;
            else tag[lk[v]]=1,q.push(lk[v]);
        }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int x,y;m--;add_edge(x,y))scanf("%d%d",&x,&y);
    FOR(i,1,n)ans+=!lk[i]&&blossom(i);
    cout<<ans<<'\n';
    FOR(i,1,n)cout<<lk[i]<<' ';
    return 0;
}