带树开花 - 带花树

带花树主要用来找一般图的最大匹配。

例题：带花树例题

如果是二分图，我们可以很简单的用匈牙利或者网络流等等方法找出来最大匹配。

但是如果不是二分图呢？（有奇环）

我们就需要用到带花树了。

主要步骤：

首先，奇环中有2k+1个点，所以最多有k组匹配。这就是说，有一个点没有匹配，即这个点在环内两边的连边都不是匹配边，也只有这个点可以向环外连边。

所以我们就可把整个奇环缩成一个点。缩完点后的图如果可以找到一条增广路，那么原图中也可以找到一条增广路，因为如果增广路经过奇环那么奇环内的增广路可以还原出来。

搜索到了一个未标记的点，有两种情况。如果这个未标记点有匹配，那么把这个点设为B类点，它的匹配点设为A类点，加入队列继续增广。如果这个点没有匹配，又因为我们是从一个未匹配点开始进行搜索的，所以这说明我们找到了一条增广路，沿着过来的边找回去，展开带花树，修改搜索的过程中，如果我们遇到了偶环，那么不管它，因为它不会影响求解。如果遇到了一个奇环，那么我们找到当前点x和找到的点v，求出他们的最近公共花祖先，然后把环缩掉。这里我们用并查集实现。

最后在这里，祝福chh生日快乐！！，EC拿牌！！！

总时间复杂度： O(n^3)

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=510,M=3e5+10;
int n,m,f[N],match[N],res,pre[N],col[N],cnt,tic[N];
int head[N],nex[M],to[M],tot;
queue<int> q;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline int lca(int x,int y){
	cnt++;
	while(1){
		if(x){
			x=find(x);	
			if(tic[x]==cnt)	return x;
			else	tic[x]=cnt,x=pre[match[x]];	
		}
		swap(x,y);
	}
}
void shrink(int x,int y,int p){
	while(find(x)!=p){
		pre[x]=y,y=match[x];
		if(col[y]==2)	col[y]=1,q.push(y);
		if(find(x)==x)	f[x]=p;
		if(find(y)==y)	f[y]=p;
		x=pre[y];
	}
}
inline int check(int s){
	for(int i=1;i<=n;i++)	f[i]=i,pre[i]=col[i]=0;
	while(q.size())	q.pop();	q.push(s);	col[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(col[to[i]]==2||find(to[i])==find(u))	continue;
			if(!col[to[i]]){
				col[to[i]]=2,pre[to[i]]=u;
				if(!match[to[i]]){
					for(int j=to[i],t,last;j;j=last){
						last=match[t=pre[j]];
						match[j]=t,match[t]=j;
					}
					return 1;
				}
				col[match[to[i]]]=1;	q.push(match[to[i]]);
			}else if(col[to[i]]==1){
				int l=lca(u,to[i]);
				shrink(u,to[i],l); shrink(to[i],u,l);
			}
		}
	}
	return 0;
}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b;i<=m;i++)	scanf("%d %d",&a,&b),add(a,b),add(b,a);
	for(int i=1;i<=n;i++)	res+=(!match[i]&&check(i));
	cout<<res<<endl;
	for(int i=1;i<=n;i++)	printf("%d ",match[i]);puts("");
	return 0;
}