对于一般的二分图匹配我们肯定会想到匈牙利算法，但是如果图中出现奇环怎么办？此时匈牙利算法就不可以了，就需要另一个算法：带花树算法
主要就是为了解决奇环的问题
我们匹配时会发现，如果存在奇环，传统的匈牙利算法在一个奇环里至少有一个点不能匹配，那么干脆就把这个奇环缩成一个点（也叫开花，这就是算法名字的由来），在处理到奇环的时候把它缩成一个点，路径取反的时候再暴力展开一个个取反。
缩点用并查集来维护

流程：

参考代码
我们给所有点黑白染色。假设开始增广的点是黑点。把所有黑点压进队列中顺次处理。对于一个黑点u，找与他相邻的点v，会出现一下四种情况：

1、u,v已经被缩成一个点了（这两个点在一朵花里），跳过。

2、v是白点，说明已经被匹配了，也就是偶环，跳过。

3、v还没有被染色。那就先把这个点染成白的，然后尝试与u匹配。如果v还没有匹配就匹配上，增广成功，然后沿增广路取反。如果v已经被匹配了，那么匹配他的点就是个黑点，染色，然后压进队列。

4、v也是黑点。这时候染色发生了冲突，说明遇见了奇环。这时候就需要找到两个点在带花树中的lca，然后把这整个环缩成一个点。（直接开花。）

缩点（开花）过程：
１、找x和y的LCA（的根）L。找LCA可以用各种方法。。。直接朴素也行。
２、在pre数组中把x和y接起来（表示它们形成环了！）
3、从x、y分别走到L，维护并查集使得变成一棵树，同时沿路把pre数组连接起来。

题目：

UOJ79 一般图最大匹配
从前一个和谐的班级，所有人都是搞OI的。有 n 个是男生，有 0 个是女生。男生编号分别为 1,…,n。
现在老师想把他们分成若干个两人小组写动态仙人掌，一个人负责搬砖另一个人负责吐槽。每个人至多属于一个小组。
有若干个这样的条件：第 v 个男生和第 u 个男生愿意组成小组。
请问这个班级里最多产生多少个小组？

题解：

就是带花树的模板题

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510;
const int M = 3e5+10;
struct node{ int to,nxt; }g[M];
int head[N],cnt;
int vis[N],match[N],f[N],pre[N],Id,id[N];
//vis[i]: 0(未染色) 1(黑色) 2(白色)
//match[i]: i的匹配点
//f[i]: i在带花树中的祖先
//pre[i]: i的非匹配边的另一点 
//id: 找LCA用 
int n,m,ans,u,v;
queue<int> q;
void Init()
{
    Id=ans=cnt=0;
    for(int i=1;i<=n;i++)
        head[i]=-1,id[i]=match[i]=0;
}
void add(int u,int v){ g[cnt]=node{v,head[u]},head[u]=cnt++; }
int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); }
//查询x和y在带花树中的LCA 
int LCA(int x,int y)
{
    //沿着增广路向上找lca 
    for(++Id;;swap(x,y))//x,y交替向上 
        if(x)
        {
            x=getf(x);//有可能环中有环(花中有花)，所以用并查集找祖先，只处理祖先节点 
            if(id[x]==Id) return x; //x,y在同一环中，一定会找到已被编号的点，该点即为LCA。 
            else id[x]=Id,x=pre[match[x]];//给点编号，并沿着非匹配边向上找        
        }
}
//缩点（开花 
void blossom(int x,int y,int l)//，将x、y到LCA(l)路径中的点，缩为一点int l)
{ 
    while(getf(x)!=l)
    {
        //增广路取反 
        pre[x]=y;
        y=match[x];
        //如果x、y的奇环中有白点，将其染为黑点，放入队列，让其去找不是环中的匹配点    
        if(vis[y]==2) vis[y]=1,q.push(y);
        //只改变是根的点 
        if(getf(x)==x) f[x]=l;
        if(getf(y)==y) f[y]=l;
        //增广路取反 
        x=pre[y];
    } 
}
bool aug(int s)
{
    //每次都以s为起点bfs，建带花树 
    for(int i=1;i<=n;i++)
        vis[i]=pre[i]=0,f[i]=i;    
    while(!q.empty()) q.pop();

    q.push(s),vis[s]=1;
    while(!q.empty())
    {
        u=q.front();q.pop();
        for(int i=head[u];~i;i=g[i].nxt)
        {
            v=g[i].to;
            //如果已经在同一个环(花)中或者是白点(意为这已经有匹配点)，只接跳过 
            //这种情况不会增加匹配数 
            if(getf(u)==getf(v)||vis[v]==2) continue;
            //如果没有被染色 
            if(!vis[v])
            {
                //先染为白色，将前继点指向u 
                vis[v]=2;
                pre[v]=u;
                //如果没有被匹配过，直接匹配成功 
                if(!match[v])
                {
                    //增广路取反 
                    for(int x=v,last;x;x=last)
                        last=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;        
                    return 1;
                }
                //如果被匹配过，则把匹配v的点染为黑色，放入队列中    
                vis[match[v]]=1;
                q.push(match[v]);
            }
            //v是黑色，形成奇环，则缩点(开花)。 
            else 
            {
                int lca=LCA(u,v);
                blossom(u,v,lca);
                blossom(v,u,lca);
            }
        }    
    }
    return 0;
}
int main(void)
{
    while(~scanf("%d%d",&n,&m))    
    {
        Init();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);    
        }        
        for(int i=1;i<=n;i++)
            if(!match[i]&&aug(i))
                ans++;    
        printf("%d\n",ans);
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i]," \n"[i==n]);
    }
    return 0;    
}