板子：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 10010 10 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,sett,father[maxn],pre[maxn],match[maxn],vis[maxn],id[maxn],dl[maxn*10],head,tail,ans; 13 14 vector<llg> a[maxn]; 15 16 llg find(llg x){if (father[x]!=x) father[x]=find(father[x]); return father[x];} 17 18 llg lca(llg x,llg y) 19 { 20 sett++; 21 while (vis[x]!=sett) 22 { 23 if (x) 24 { 25 x=find(x); 26 if (vis[x]==sett) return x; 27 vis[x]=sett; 28 if (match[x]!=0) x=find(pre[match[x]]); 29 else x=0; 30 } 31 else 32 swap(x,y); 33 } 34 return x; 35 } 36 37 void change(llg x,llg y,llg fa) 38 { 39 llg z; 40 while (find(x)!=fa) 41 { 42 pre[x]=y; z=match[x]; 43 if (id[z]==1) {id[z]=0,dl[++tail]=z;} 44 father[z]=fa; 45 father[x]=fa; 46 y=z; x=pre[y]; 47 } 48 } 49 50 bool bfs(llg p) 51 { 52 llg x,w,v; 53 for (llg i=1;i<=n;i++) id[i]=-1,father[i]=i; 54 head=0,tail=1,dl[1]=p; id[p]=0; 55 do 56 { 57 x=dl[++head],w=a[x].size(); 58 for (llg i=0;i<w;i++) 59 { 60 v=a[x][i]; 61 if (id[v]==-1) 62 { 63 pre[v]=x; 64 id[v]=1; 65 if (!match[v]) 66 { 67 llg last,t,now=v; 68 while (now!=0) 69 { 70 t=pre[now],last=match[t]; 71 match[t]=now; match[now]=t; 72 now=last; 73 }//把原lai的匹配和非匹配bian取反 74 return 1; 75 } 76 id[match[v]]=0,dl[++tail]=match[v]; 77 } 78 else 79 if (id[v]==0 && find(v)!=find(x)) 80 { 81 llg dad=lca(x,v); 82 change(x,v,dad); 83 change(v,x,dad); 84 } 85 } 86 }while (head!=tail); 87 return 0; 88 89 } 90 91 void init() 92 { 93 scanf("%lld%lld",&n,&m); 94 llg x,y; 95 for (llg i=1;i<=m;i++) 96 { 97 scanf("%lld%lld",&x,&y); 98 a[x].push_back(y),a[y].push_back(x); 99 } 100 } 101 102 int main() 103 { 104 yyj("a"); 105 init(); 106 for (llg i=1;i<=n;i++) if (!match[i] && bfs(i)) ans++; 107 cout<<ans<<endl; 108 for (llg i=1;i<=n;i++) printf("%lld ",match[i]); 109 return 0; 110 }