一般图最大匹配问题

二分图上的最大匹配可以用匈牙利算法，时间复杂度 $O(n^2)$ 。

在一般图上因为有奇环所以匈牙利算法不再适用，我们可以用带花树算法来解决奇环。

带花树算法

带花树 $=$ 匈牙利 $+$ 缩花处理奇环。

与匈牙利算法本质类似，就是每次不断尝试找到一条交错路，然后交换路上的匹配边与非匹配边。

首先，不用 $DFS$ 进行增广而是使用 $BFS$ ，在 $BFS$ 的时候对整张图进行染色，我们把在匹配中的点分为两种，一种是匹配点（黑），标为 $1$ ，另一种为被匹配点（白），标为 $2$ ，最后没有经过的点标为 $0$ 。

然后我们记录两个数组 $pre$ 表示在 $bfs$ 搜索树上 $i$ 的父亲， $match$ 表示和 $i$ 匹配的点，显然 $match$ 是黑点和白点之间的对应，然后从 $1$ 到 $n$ 枚举每个点作为根，要求这个点为黑点，然后我们在增广的时候要求搜索树上黑点可以有多个孩子，但是白点只能有一个孩子，就是他的匹配点，也就是说对于所有黑点 $match=pre$ ，类似匈牙利，我们只遍历所有黑点的出边，也只把黑点加入队列中，对于白点我们直接通过 $match$ 找到它儿子那个黑点。

我们在枚举黑点的出边 $(u\to v)$ 时，如果 $v$ 没有访问过，那么 $v$ 就应该是一个白点，如果这个白点有 $match$ ，那么就把那一个黑点加入队列中，否则的话我们找到的一条交错路，直接交换这条路的匹配边和非匹配边，退出。

如果 $v$ 访问过并且是白点，那么显然这个点的匹配我们已经找过了，直接 $continue$ 。

如果 $u$ 和 $v$ 在同一个奇环里，由于 $u$ 是黑点，我们也不需要修改环的匹配， $continue$ 。

最后的一个问题，如果 $v$ 也是一个黑点，那么我们就找到了一个奇环，考虑怎么处理：

首先因为是 $BFS$ 而且找到的是奇环，那么 $u$ 和 $v$ 深度相同，并且在环上的 $LCA$ 一定是黑点，因为只有黑点有多个儿子，那么我们可以找到这个 $LCA$ ，并暂时性的把他们在并查集中都连向 $LCA$ ，因为奇环一定有 $2k+1$ 个点，我们可以构成 $k$ 组匹配，再把最后一个点和外边连，也就是说一个奇环相当于一个黑点，因此我们可以把他们暂时缩起来，因为每次循环都要重置并查集，然后我们再把环上所有的黑点都放到队列里尝试增广，实际上就是把这个花放到队列里。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 510

#define MAXM 125000

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int f[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int col[MAXN];

int pre[MAXN];

int match[MAXN];

int tag[MAXN],tim = 0;

int LCA(int u,int v)

{

	++tim;

	u = find(u);v = find(v);

	while(tag[u] != tim)

	{

		tag[u] = tim;

		u = find(pre[match[u]]);

		if(v)swap(u,v);

	}

	return u;

}

queue<int> q;

void blossom(int u,int v,int lca)

{

	while(find(u) != lca)

	{

		pre[u] = v;v = match[u];

		if(col[v] == 2)col[v] = 1,q.push(v);

		if(find(u) == u)f[u] = lca;

		if(find(v) == v)f[v] = lca;

		u = pre[v];

	}

	return;

}

int work(int s)

{

	memset(f,0,sizeof(f));

	memset(pre,0,sizeof(pre));

	memset(col,0,sizeof(col));

	while(!q.empty())q.pop();

	q.push(s);col[s] = 1;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			int v = e[i].to;

			if(find(k) == find(v))continue;

			if(col[v] == 2)continue;

			if(col[v] == 0)

			{

				col[v] = 2;pre[v] = k;

				if(match[v] == 0)

				{

					for(int x = v,pr;x;x = pr)

					{

						pr = match[pre[x]];

						match[x] = pre[x];match[pre[x]] = x;

					}

					return 1;

				}

				col[match[v]] = 1;

				q.push(match[v]);

			}

			else

			{

				int lca = LCA(k,v);

				blossom(k,v,lca);

				blossom(v,k,lca);

			}

		}

	}

	return 0;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = rd();b = rd();

		add(a,b);

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)if(!match[i])ans += work(i);

	cout << ans << endl;

	for(int i = 1;i <= n;++i)printf("%d ",match[i]);

	cout << endl;

	return 0;

}