两年前就听hgr说了这个东西,一直打算找时间学习一个,结果一直鸽到了现在。。

我们都知道一般图最大匹配可以用带花树算法来做。关于带花树算法,网上有很多非常不错的学习资源(比如这个),所以算法的大体思路这里就不再赘述了。

这个算法的细节比较多,没有一个比较深刻的认识的话,感觉好像很容易写错的样子。为了明确细节,我们先来强调一下算法的基本概念。在这个算法当中,我们有两个概念(这个概念是我自己瞎脑补的,所以听起来可能比较扯淡),一个是“原交错树”,一个是“缩花后的交错树”。原交错树就是未经过缩花的交错树,我们bfs扩展的就是这棵交错树。在这棵交错树上,是可能会出现两个偶点相邻的情况的。为了避免这种情况,我们还需要另一棵“缩花后的交错树”,原交错树中的一个花,在这棵交错树上就会被缩成一个点,缩花后的点可以用这朵花的花托来表示。这样的话,就不会出现两个偶点相邻,就可以跟二分图匹配一样去找增广路了。具体实现上,缩花后的交错树中的每个节点,都对应了原交错树中的一个点集,可以用并查集来维护。

我们知道,同一朵花的每个点,不管是奇点还是偶点,都可以通过绕花的方式找到一条到花托的交错路。所以,在找交错路径的时候,可以把这些点都看作同一个偶点,这也就是“缩花”的本质。对于一个点,它在并查集中的根,表示了这个点通过绕花能绕到的最高点(最高指的是在交错树中的深度最小)。同时,对于一个被缩起来的奇点,我们可以在原交错树上记录这个点应该如何绕花,也就是记下把对应花的横叉边。这样,我们只要利用记下的信息,就能找到原交错树中的某个点到根节点的交错路径。

现在,这些细节就很明确了:所有跟缩花以及寻找增广路有关的操作,都应该在使用并查集的缩花后的交错树上进行。而发现增广路后,我们需要在原交错树上沿着增广路翻转匹配边,这里可以利用之前记录的花的信息来处理。注意后一步操作是跟缩花后的交错树无关的,所以不需要用到并查集。

另外,在广搜的过程中,队列中应该只记录待扩展的偶点。对于那些在缩花过程中被缩起来的奇点,他们也可以被看成偶点,所以缩花时也要把缩起来的所有奇点加入队列。关于如何找交错树上的LCA,我的做法是类似树链剖分那样,记录每个点在原交错树中的深度,每次选取对应花托较深的那个点往上跳,直到两个点跳到了同一个花内。这样写感觉细节不多,比沿路打标记的做法要好写一点。

附上代码实现一份。由于写法奇特,在uoj上垫底了。。

#include <bits/stdc++.h>
#define MAXN 3010
using namespace std;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[1000000];

int n,m;
int g[MAXN],nume;
//访问状态,0:未访问,1:奇点,2:偶点
int visit[MAXN];
int ans;
int nump;
//p表示每个点匹配点(0表示未匹配),pre表示每个点在原交错树上的父亲
int p[MAXN],pre[MAXN];
//c1,c2记录的是每个奇点对应的花的横叉边的两个端点
int c1[MAXN],c2[MAXN];
//每个点在原交错树上的深度
int dep[MAXN];
static queue<int> Q;

//并查集
int f[MAXN];
int getf(int x){ if(f[x]==x) return x; return f[x]=getf(f[x]); } 
void merge(int x,int y){ f[getf(x)]=getf(y); }

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
    e[nume]=edge(u,g[v]);
    g[v]=nume++;
}

int getLCA(int x,int y){
    while(getf(x)^getf(y)){
        if(dep[f[x]]<dep[f[y]]) x^=y^=x^=y;
        x=pre[f[x]];
    }
    return getf(x);
}

//把x到y的交错路径翻转(为了好写用了递归,所以比较慢...)
void go(int x,int y,int d){
    //GO is GOD
    if(x==y) return;
    if(!d){
        p[x]=pre[x];
        p[pre[x]]=x;
        go(pre[x],y,1);
    }else{
        if(visit[x]==2) go(pre[x],y,0);
        else{
            //绕花
            int t1=c1[x],t2=c2[x];
            p[t1]=t2;
            p[t2]=t1;
            go(t1,x,1);
            go(t2,y,1);
        }
    }
}

//缩花,并把奇点加入队列
void gao_blossom(int x,int y,int lca){
    int _x=x,_y=y;
    x=getf(x);
    while(x^lca){
        int t=pre[x];
        Q.push(t);
        c1[t]=_x; c2[t]=_y;
        int t2=getf(pre[t]);
        merge(x,t);
        merge(t,t2);
        x=t2;
    }
}

bool gao(int rt){
    for(int i=1;i<=n;i++) visit[i]=0,f[i]=i;
    while(!Q.empty()) Q.pop();
    Q.push(rt);
    visit[rt]=2;
    dep[rt]=0;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=g[x];~i;i=e[i].next){
            int y=e[i].to;
            if(getf(x)==getf(y)) continue;
            if(!visit[y]){
                visit[y]=1;
                if(!p[y]){
                    //找到增广路
                    pre[y]=x;
                    go(y,rt,0);
                    return 1;
                }else{
                    //扩展交错树
                    int z=p[y];
                    visit[z]=2;
                    pre[y]=x;
                    pre[z]=y;
                    dep[y]=dep[x]+1;
                    dep[z]=dep[y]+1;
                    Q.push(z);
                }
            }else if(visit[getf(y)]==2){
                //发现花
                int lca=getLCA(getf(x),getf(y));
                gao_blossom(x,y,lca);
                gao_blossom(y,x,lca);
            }
        }
    }
    return 0;
}

int main(){
    memset(g,-1,sizeof g);
    ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!p[i] && gao(i))
            ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) printf("%d ",p[i]);
    return 0;
}