[uoj79][帶花樹]一般圖最大比對

傳送門：

http://uoj.ac/problem/79

一般圖最大比對不會做怎麼辦。看了一晚上的帶花樹沒看明白。

思考一下帶花樹的核心是bfs()+縮花+增廣

bfs大家都會，縮花是整個算法的難點。

玄學亂搞

假設我們不想寫帶花樹并需求一個通常情況下可以解決一般圖最大比對問題的做法時，我們可以忽略掉縮花的過程然後随機增廣，将未比對點随機轉移，通常可以在n^2時間内出正确解。

帶花樹

建議先看一下别人的講義再看我這份，僅僅是部分補充。

https://www.cnblogs.com/owenyu/p/6858508.html

在二分圖比對中，我們通常使用匈牙利算法（fake）來解決最大比對問題。考慮在一般圖上使用匈牙利，我們發現有的點既成為了内點又成為了外點。思考在二分圖上顯然是不會出現這種情況的。容易發現這種情況下肯定是出現了一個奇環，而且這個環上如果有一個點出現了新的比對，顯然這個環上的所有點都得到了比對，那麼我們的比對數+1（增廣成功）。可以簡單的推斷出奇環上所有點的比對情況是等價的，是以我們可以把它們縮起來。

那麼我們要怎麼實作這個做法呢？我一開始的想法是暴力的縮點，縮掉的點就直接不存在了。觀察了一波網上大爺們的實作，我們并不需要顯式的維護縮起來的點和重建立邊，而是考慮使用一個并查集來簡單的維護花根，用match數組表示一個點的配偶是誰，pre數組記錄當一個點的配偶得到比對時，這個點應該和誰比對。考慮到一個花的形态就是從一個root走出2條未比對邊，然後這兩條邊走到了一起，那麼縮點實際上非常簡單了，我們一直走他的祖先，把一路上的點的花根全部指向root。理論上一個花中的節點已經全部指向花根了，并且在我的了解中這些點已經完全沒有用了，因為這些結點的比對狀況相同，是以這些點的match等等我們也應該全部不關心，因為答案其實就是所有花根的圖中的match數+花根size/2，但是因為我們是非顯性維護的花，如果不把這些玩意的match維護出來的話，我們在縮點的時候就不好走他的祖先了，而且隊列中的點如果僅僅是作為花根的一個延伸，那我們bfs的時候還得先把這個花根的兒子全部找出來，那我們還不如把它縮了。而且有的題要求輸出match方案，是以還是用這種寫法好點。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int N=;
const int M=;
int n,m;
namespace flowey
{
    int pre,tim,t,w,q[M],fa[N],last[N],match[N],col[N];
    int tot,nex[M],go[M],fir[N],vis[N];
    inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline void add(int x,int y) {nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;}
    inline int lca(int x,int y)
    {
        for(++tim,x=find(x),y=find(y);;swap(x,y))
        if(x)
        {
            if(vis[x]==tim) return x;
            vis[x]=tim;
            x=find(last[match[x]]);
        }
    }
    inline void link(int x,int y,int rt)
    {
        while(find(x)!=rt)
        {
            last[x]=y;
            if(fa[x]==x) fa[x]=rt;
            y=match[x];
            x=last[y];
            if(fa[y]==y) fa[y]=rt;
            if(col[y]==) col[q[++w]=y]=;
        }
    }
    inline int bfs(int X)
    {
        int u,e,v;
        for(int i=;i<=n;++i) fa[i]=i,col[i]=last[i]=;
        t=;col[q[w=1]=X]=;
        while(t<w)
        {
            u=q[++t];
            for(e=fir[u];v=go[e],e;e=nex[e])
            if(!col[v])
            {
                last[v]=u;
                if(!match[v])
                {
                    for(;u;v=pre,u=last[v])
                    //這個時候已經不需要像link一樣修改last了，已經沒有意義了 
                    {
                        pre=match[u];
                        match[u]=v;
                        match[v]=u;
                    }
                    return ;
                }
                col[v]=;
                col[q[++w]=match[v]]=;
            }
            else if(col[v]==&&find(u)!=find(v))
            {
                int k=lca(u,v);
                link(u,v,k);link(v,u,k);
            }
        }
        return ;
    }
}
int main()
{
//  freopen("79.in","r",stdin);
    using namespace flowey;
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    int ans=;
    for(int i=;i<=n;++i)
    if(!match[i]) ans+=bfs(i);
    cout<<ans<<endl;
    for(int i=;i<=n;++i) printf("%d ",match[i]);
}