Description
每天都要考，每天都要讲，大家注意力都集中不起来了，每天听解题报告时都有人交头接耳（也包括我，呵呵）。这样做大大的影响的学习效率（可能吧）。于是，有些好奇心重的同学就开始研究，怎样才会最吵。培训的总共有N个人，但不是每两人之间都讲话，只有一些人有话题聊，而且一个人可能会和多个人有话题（共M对人）。如果所有同学都说在话，教室里最吵。你的任务就是求出把说话者对数控制在多少人以内，无论如何教室里不会变得最吵？注意：A和B说话，同时B和C说话，这算两对人说话。
Input
第一行两个整数N,M。接下来M行，每行两个整数x,y表示x和y有话题聊。
Output
一行，一个整数表示要把说话者对数控制在多少以内，无论如何教室里不最吵。
若有孤立点，则答案为M，否则设最少用k条边覆盖所有点，则答案为k-1
k=N-最大匹配
#include<bits/stdc++.h> const int N=10007; int es[N],enx[N],e0[N],ep,q[N],ql,qr,n,m,f[N],nx[N],pv[N],t[N],ts[N],tk=0,ans=0; void ae(int a,int b){ es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; } int get(int x){return x!=f[x]?f[x]=get(f[x]):x;} int lca(int x,int y){ ++tk; while(1){ if(x){ x=get(x); if(ts[x]==tk)return x; ts[x]=tk; x=pv[nx[x]]; } std::swap(x,y); } } void mg(int a,int b){ while(a!=b){ int w=nx[a],u=pv[w]; if(get(u)!=b)pv[u]=w; if(t[a]==2)t[q[++qr]=a]=1; if(t[w]==2)t[q[++qr]=w]=1; if(a==f[a])f[a]=b; if(w==f[w])f[w]=b; a=u; } } int bfs(int w0){ for(int i=1;i<=n;++i)f[i]=i,pv[i]=0,t[i]=0; ql=qr=0; q[++qr]=w0; while(ql!=qr){ int w=q[++ql]; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u==nx[w]||get(w)==get(u)||t[u]==2)continue; if(t[u]==1){ int v=lca(w,u); if(get(w)!=v)pv[w]=u; if(get(u)!=v)pv[u]=w; mg(w,v);mg(u,v); }else if(nx[u]){ pv[u]=w; t[u]=2; t[q[++qr]=nx[u]]=1; }else{ while(w){ int a=nx[w]; nx[w]=u;nx[u]=w; u=a; w=pv[u]; } return 1; } } } return 0; } int main(){ while(scanf("%d%d",&n,&m)==2){ memset(e0,0,sizeof(int)*(n+1)); memset(nx,0,sizeof(int)*(n+1)); ep=2; for(int i=1,a,b;i<=m;++i){ scanf("%d%d",&a,&b); ae(a,b); } for(int i=1;i<=n;++i)if(!e0[i]){ printf("%d\n",m); goto o; } ans=0; for(int i=1;i<=n;++i)if(!nx[i])ans+=bfs(i); printf("%d\n",n-ans-1); o:; } return 0; }