1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
using namespace std;
const int N=1005;
int T,n,m,e,cnt,tot,ans,hd[N],p[N],match[N],pre[N],vst[N],dfn[N];
queue<int>q;
struct edge{int t,nxt;}es[N*N];
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
inline void read(register int&x){
x=0;int s=gc();
while(!isdigit(s))s=gc();
while(isdigit(s))x=(x<<3)+(x<<1)+s-'0',s=gc();
}
void print(register int x){
if(x>9)print(x/10);
putchar(x%10+'0');
}
inline void Add(register int u,register int v){es[++tot]=(edge){v,hd[u]};hd[u]=tot;}
inline void add(register int u,register int v){Add(u,v),Add(v,u);}
int find(register int x){return x==p[x]?x:p[x]=find(p[x]);}
inline int lca(register int u,register int v){
for(++cnt,u=find(u),v=find(v);dfn[u]!=cnt;){
dfn[u]=cnt;
u=find(pre[match[u]]);
if(v)swap(u,v);
}
return u;
}
inline void blossom(register int x,register int y,register int w){
while(find(x)!=w){
pre[x]=y,y=match[x];
if(vst[y]==2)vst[y]=1,q.push(y);
if(find(x)==x)p[x]=w;
if(find(y)==y)p[y]=w;
x=pre[y];
}
}
inline int aug(register int s){
if((ans+1)*2>n)return 0;
for(register int i=1;i<=n;++i)p[i]=i,vst[i]=pre[i]=0;
while(!q.empty())q.pop();
for(q.push(s),vst[s]=1;!q.empty();q.pop())
for(register int u(q.front()),i(hd[u]),v,w;i;i=es[i].nxt){
if(find(u)==find(v=es[i].t)||vst[v]==2)continue;
if(!vst[v]){
vst[v]=2;pre[v]=u;
if(!match[v]){
for(register int x=v,lst;x;x=lst)lst=match[pre[x]],match[x]=pre[x],match[pre[x]]=x;
return 1;
}
vst[match[v]]=1,q.push(match[v]);
}else blossom(u,v,w=lca(u,v)),blossom(v,u,w);
}
return 0;
}
int main(){
read(n),read(m);
for(register int i=1,u,v;i<=m;i++)read(u),read(v),add(u,v),add(v,u);
for(register int i=n;i;--i)if(!match[i])ans+=aug(i);
print(ans),putchar('\n');
for(register int i=1;i<=n;i++)print(match[i]),putchar(' ');
return 0;
}
|