题解
板子！我相信其实没人来看我的板子！但是为了防止我忘记，我还是要写点什么
我们考虑二分图，为什么二分图就能那么轻松地写出匹配的代码呢？因为匹配只会发生在黑点和白点之间，我们找寻增广路，必然是一黑一白一黑一白这么走
然而，一般图由于有了奇环，事情变得不妙了啊
奇环上的所有点，可以是……任意的奇偶性（起点到它的距离的奇偶性，可以是非简单路径）
那么我们就让任意奇偶性的点可以进行匹配就可以了，我们通过pre维护出一条路径到达根节点
怎么维护呢？缩花！
花？什么是花？
花就是奇环，我们找到花托（两个点的最近公共祖先），从两个点构建一条能走到花托的路径
如何构建
对于(u,v)和花托f
我们让u的pre走到v，然后令u跳到u匹配点的pre,v变成u的匹配点，继续这个操作，同时把这个匹配点改成偶点(可进行增广）
对v走到花托走到f进行类似的操作
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 505
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int to,next;
}E[MAXN * MAXN * 2];
int sumE,head[MAXN];
int N,M,fa[MAXN],pre[MAXN],matk[MAXN],sta[MAXN];
int Q[MAXN],L,R;
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
int getfa(int x) {
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
int lca(int x,int y) {
static int vis[MAXN],Tim;
++Tim;
while(1) {//每个点都尝试走一步
x = getfa(x);
if(x) {
if(vis[x] == Tim) {
return x;
}
else vis[x] = Tim,x = pre[matk[x]];
}
swap(x,y);
}
}
void blossom(int u,int v,int flower_root) {
while(getfa(u) != flower_root) {
pre[u] = v;
//我们每个点既然都是奇偶难分（雾）
//就构建出一条这个点走到花托的交错路
//构建方法就是顺着匹配边往上跳
//这个时候我们碰到的匹配点还都以为自己是偶点= =（奇怪的叙述）
int m = matk[u];
if(sta[m] == 1) {sta[m] = 0;Q[++R] = m;}
//把所有以为自己是奇点的人告诉他们可以当偶点啦
if(u == fa[u]) fa[u] = flower_root;
if(m == fa[m]) fa[m] = flower_root;
v = m,u = pre[m];
}
}
bool match(int s) {
//sta : -1 未访问 0:偶点（起始点） 1:奇点
//pre : 交错树上的父亲，任意一点顺着当前自己的匹配点的pre会走到树根，也就是还原出了交错路
L = 1,R = 0;Q[++R] = s;
memset(sta,-1,sizeof(sta));
memset(pre,0,sizeof(pre));
sta[s] = 0;//起点是偶点
for(int i = 1 ; i <= N ; ++i) fa[i] = i;
while(L <= R) {
int u = Q[L++];
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(sta[v] == -1) {
pre[v] = u;sta[v] = 1;
if(!matk[v]) {
for(int j = u , k = v,last; ; j = pre[k = last]) {
last = matk[j],matk[j] = k;matk[k] = j;
if(!last) break;
}//顺着pre节点找交错路，全部取反
return 1;
}
sta[matk[v]] = 0;
Q[++R] = matk[v];
}
else if(getfa(v) != getfa(u) && !sta[v]) {
int f = lca(u,v);blossom(u,v,f);blossom(v,u,f);
//两个偶点，缩花，两条路径爬到父亲
}
}
}
return 0;
}
void Init() {
read(N);read(M);
int u,v;
for(int i = 1 ; i <= M ; ++i) {
read(u);read(v);
add(u,v);add(v,u);
}
}
void Solve() {
int ans = 0;
for(int i = 1 ; i <= N ; ++i) {
if(!matk[i] && match(i)) ++ans;
}
out(ans);enter;
for(int i = 1 ; i <= N ; ++i) {
out(matk[i]);
if(i == N) enter;
else space;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}
//5aaC5p6c5oiR5LiK5LiN5LqGdGh177yM5oiR5bCx5YaN5Lmf6KeB5LiN5Yiw54yr6ZSf5LqG
//4oCm4oCm54yr6ZSf55yf5Y+v54ix