蒟蒻的带花树板子

在匈牙利的基础上增加对奇环的讨论

把基环缩成一个黑点

inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int getlca(int x,int y){
    tot++;
    x=getfa(x),y=getfa(y);
    while(dfn[x]!=tot){
        dfn[x]=tot;
        x=getfa(pre[match[x]]);
        if(y) swap(x,y);
    }
    return x;
}
void build(int x,int y,int w){
    while(getfa(x)!=w){
        pre[x]=y,y=match[x];
        if(col[y]==2) col[y]=1,Q.push(y);
        if(getfa(x)==x) fa[x]=w;
        if(getfa(y)==y) fa[y]=w;
        x=pre[y];
    }
}
bool bfs(int x){
    memset(pre,0,sizeof(pre));
    memset(col,0,sizeof(col));
    for(int i=1;i<=N;i++) fa[i]=i;
    while(!Q.empty()) Q.pop();
    col[x]=1;
    Q.push(x);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=last[u];i;i=Next[i]){
            int v=to[i];
            if(getfa(u)==getfa(v)||col[v]==2) continue;
            if(!col[v]){
                col[v]=2;
                pre[v]=u;
                if(!match[v]){
                    for(int j=v,nxt;j;j=nxt){
                        nxt=match[pre[j]];
                        match[pre[j]]=j,match[j]=pre[j];
                    }
                    return 1;
                }
                col[match[v]]=1;
                Q.push(match[v]);
            }
            else{
                int w=getlca(u,v);
                build(u,v,w);
                build(v,u,w);
            }
        }
    }
    return 0;
}