带花树算法学习小记
众所周知，带花树算法用来解决一般图最大匹配问题。
因为人很菜理解不清楚，所以建议对板理解。
以下都是本人的感性理解，有不严谨的说法请包涵。
参考资料：
https://blog.bill.moe/blossom-algorithm-notes/
https://www.cnblogs.com/cjyyb/p/8719368.html
同样是找增广路。增广路定义为一条路径(p_1,p_2,dots,p_k)，满足(p_2,p_3)匹配，(p_4,p_5)匹配……(p_{k-2},p_{k-1})匹配。(p_1)和(p_k)不在匹配中、
如果找到了增广路，把增广路上点调整一下匹配关系，就可以使匹配数增多。
设(bel_x)表示(x)和哪个点匹配。还有(pre_x)表示(BFS)树上的前驱。
找增广路大概流程：BFS，遍历过的点要记录颜色。(S)不在匹配中，(S)为起点，一开始(S)为黑色。
设当前点为(u)，枚举其一条边(v)。
- 如果(v)没有被遍历过：（1）(v)不在匹配中，此时找到增广路。（2）(v)在匹配中，把(v)标记为白点，(bel_v)标记为黑点，把(bel_v)丢入队列。
- 如果(v)被遍历过：
- 如果(v)为白点，不管它。
- 如果(v)为黑点，进行开花操作。
算法核心：开花。
如果开花一定是找到了个奇环。定义此时(u,v)在BFS树上的LCA为花根，记为(rt)。
考虑从花上的某个点出去，并且找到了增广路。那么一定可以从(rt)开始（其中(rt)是黑点），可以通过走花的一边，使得走的这一边都是白点-黑点交替。（这种说法并不准确，看着办吧）这条路径是头是黑点，尾是黑点，所以可以看成把花缩到花根上。后面找到增广路的时候就把花展开，展开的时候选一条花根到花中连出去的点的合法的路径。
实现是问题。
每个需要记录前驱。然而如果在花中可能前后两个点都是前驱，都要记下来。
为了方便实现，(pre_x)只是记(x)为白点意义下的前驱（因为在花中，(x)可能作为黑点，可能作为白点）。如果(x)为黑点，那么它往前两步是：(x o bel_x o pre_{bel_x})。这样就不需要另外记另一个前驱了。
求LCA时，轮流跳，跳到了之后打标记，直到跳到有标记的点为止。遍历次数是(2max(dis(u,rt),dis(v,rt))=O(花大小))（之前缩的花算一个点）。
开花：给花上的原来黑点的位置，计算它为白点意义下的前驱(pre_x)，此时(pre_x)将指向不同于(bel_x)的方向。并且把这些白点都标记为黑点，丢入队列（此时标黑表示是否有丢入队列。）。（然而在实现的时候，开花操作是对没有缩点的图进行操作。）
用并查集来维护出每个点当前在哪个花中。
更多细节见代码注释。
怎么网上的好多板子说总时间是(O(nm*并查集时间))，为什么我感觉下面这个照着别人板子写了板子的时间复杂度是(O(n^3))？
一次缩点会少至少两个点，所以会进行(O(n))次开花操作。然而这个板子里开花时间是(O(n))的。于是一次增广时间应该是(O(n^2))。
理论上确实也可以做(O(m))吧，就是保证如果一个点被缩掉，开花的时候就不会遍历它。但不知道有什么简洁的实现方法。
如果有神仙路过希望指点。
using namespace std;
#include <bits/stdc++.h>
#define N 1005
#define M 200005
int n,m;
struct EDGE{
int to;
EDGE *las;
} e[M*2];
int ne;
EDGE *last[N];
void link(int u,int v){
e[ne]={v,last[u]};
last[u]=e+ne++;
}
queue<int> q;
int c[N];
int bel[N],pre[N],fa[N];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int LCA(int x,int y){
static int bz[N],BZ;
++BZ,x=getfa(x),y=getfa(y);
while (bz[x]!=BZ){
bz[x]=BZ;
x=getfa(pre[bel[x]]);
if (y)//注意判断当点为0的时候不要跳
swap(x,y);
}
return x;
}
void blossom(int x,int y,int w){
//开花操作时一个一个跳，即使是被缩掉的点
while (getfa(x)!=w){//一定要这么写
pre[x]=y,y=bel[x];
if (c[y]==0) c[y]=1,q.push(y);
fa[x]=w;
fa[y]=w;
//注意不要像下面这么写，因为getfa(x)是x的祖先，到时候跳过去的时候会提前退出循环
// fa[getfa(x)]=w;
// fa[getfa(y)]=w;
x=pre[y];
}
}
int find(int S){
while (!q.empty())
q.pop();
for (int i=1;i<=n;++i){
c[i]=-1;
pre[i]=0;
fa[i]=i;
}
q.push(S);
c[S]=1;
while (!q.empty()){
int x=q.front();
q.pop();
for (EDGE *ei=last[x];ei;ei=ei->las){
int y=ei->to;
if (getfa(x)==getfa(y))//别忘了
continue;
if (c[y]==-1){
pre[y]=x;
if (!bel[y]){
for (int z=y,lst;z;z=lst)
lst=bel[pre[z]],bel[z]=pre[z],bel[pre[z]]=z;
return 1;
}
c[y]=0,c[bel[y]]=1;
q.push(bel[y]);
}
else if (c[y]==1){
int lca=LCA(x,y);
blossom(x,y,lca);
blossom(y,x,lca);
}
}
}
return 0;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
link(u,v),link(v,u);
}
int ans=0;
for (int i=1;i<=n;++i)
if (!bel[i])
ans+=find(i);
printf("%d
",ans);
for (int i=1;i<=n;++i)
printf("%d ",bel[i]);
return 0;
}