匈牙利算法寻找的增广路是有向的，其中匹配边的方向唯一，故匈牙利算法适配二分图的匹配。
对于存在奇环的一般图，匹配边在增广路中的方向不唯一，不符合匈牙利算法中 “一个点不能被访问两次” 的限制，故一般图最大匹配不能使用匈牙利算法。
带花树算法
一般图与二分图区别在于奇环的有无，对于一个大小为 \(2k+1\) 的奇环，其最多只有 \(k\) 对匹配，所以有至少一个节点能向外匹配，它可以是奇环内的任意节点。
求最大匹配时，一个奇环和一个节点等价，可以将对奇环缩点后当成二分图继续匹配。
把奇环缩成的点称为花，对原图用 bfs 寻找增广路，这棵节点可能是花的 bfs 树称带花树。
在带花树上 bfs，对访问到的节点进行黑白染色。
若起点为黑点，那么黑 \(\rightarrow\) 白的边为非匹配边，白 \(\rightarrow\) 黑的边为匹配边。
遍历黑点的出边，若访问到的点未被染色且未被匹配，此时就找到一条增广路。如果被匹配了，将该点染白，将该点的匹配点染黑并加入队列。
若访问到白点，此时找到一个偶环，不需要处理。若访问到黑点就找到了奇环，在 bfs 树上这两个点的 \(lca\) 可以确定奇环的位置，用并查集将它们缩起来。缩起来的环为黑点，将环上的白点改为黑点并加入队列中，也叫做开花。
遍历增广路可以对每个点存一个前驱 \(pre\) 表示从该点出发走一条非匹配边应该到达哪个节点。被缩掉的环的非匹配边的 \(pre\) 是双向的。
求 \(lca\) 时，每次用 \(pre\) 和 \(match\) 轮流往上跳，边跳边打标记，碰上了就是 \(lca\).
相当于暴力跳，跳完后缩点使得每次总点数都减少，时间均摊 \(O(1)\).
同理开花的复杂度也是均摊 \(O(1)\) 的。
类似启发式合并，通过缩环减少一个点的复杂度均摊 \(O(\log n)\)，找到增广路的最劣复杂度为 \(O(n+m)\).
故用带花树算法求一般图最大匹配的复杂度为 \(O(n\times(n\log n+m))=O(n^2\log n+nm)\)，由于跑不满可以当作 \(O(nm)\).
P6113 【模板】一般图最大匹配
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,ans;
vector<int>e[N];
int f[N],match[N];
int tag[N],tim,col[N],pre[N];
queue<int>q;
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int lca(int x,int y){
tim++;
while(true){
if(x){
x=find(x);
if(tag[x]==tim)return x;
tag[x]=tim,x=pre[match[x]];
}
swap(x,y);
}
return -1;
}
void blossom(int x,int y,int w){
while(find(x)!=w){
pre[x]=y,y=match[x];
col[y]=1,q.push(y);
if(find(x)==x)f[x]=w;
if(find(y)==y)f[y]=w;
x=pre[y];
}
}
bool bfs(int s){
if((ans+1)*2>n)return false;
for(int i=1;i<=n;i++)f[i]=i,col[i]=pre[i]=0;
while(!q.empty())q.pop();
q.push(s),col[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int v:e[u]){
if(find(u)==find(v)||col[v]==2)continue;
if(!col[v]){
col[v]=2,pre[v]=u;
if(!match[v]){
int x=v,y,z;
while(x){
y=pre[x],z=match[y];
match[x]=y,match[y]=x;
x=z;
}
return true;
}
col[match[v]]=1,q.push(match[v]);
}
else{
int w=lca(u,v);
blossom(u,v,w),blossom(v,u,w);
}
}
}
return false;
}
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
e[u].push_back(v),e[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(!match[i])ans+=bfs(i);
printf("%d\n",ans);
for(int i=1;i<=n;i++)
printf("%d ",match[i]);
printf("\n");
return 0;
}