欧拉回路的题；
主要利用的是并查集，为了节省时间，压缩了它的路径；
代码：
1 #include<cstdio> 2 #include<cstring> 3 #define maxn 100009 4 using namespace std; 5 6 int f[maxn],rank[maxn],du[maxn]; 7 bool vis[maxn],mark[maxn]; 8 9 void make_set(int x) 10 { 11 f[x]=x; 12 rank[x]=0; 13 } 14 15 int find(int x) 16 { 17 int p=x,k; 18 while(p!=f[p]) 19 { 20 p=find(f[p]); 21 } 22 while(x!=p) 23 { 24 k=f[x],f[x]=p,x=k; 25 } 26 return p; 27 } 28 29 void combine(int x,int y) 30 { 31 int t1=find(x); 32 int t2=find(y); 33 if(rank[t1]<rank[t2]) f[t1]=t2; 34 else 35 { 36 f[t2]=t1; 37 if(rank[t1]==rank[t2]) rank[t1]++; 38 } 39 } 40 41 int main() 42 { 43 int n,m,x,y,ans; 44 while(scanf("%d%d",&n,&m)!=EOF) 45 { 46 memset(vis,0,sizeof vis); 47 memset(du,0,sizeof du); 48 memset(mark,0,sizeof mark); 49 ans=0; 50 for(int i=0; i<m; i++) 51 { 52 scanf("%d%d",&x,&y); 53 if(!vis[x]) make_set(x),vis[x]=1; 54 if(!vis[y]) make_set(y),vis[y]=1; 55 du[x]++,du[y]++; 56 combine(x,y); 57 } 58 for(int i=1; i<=n; i++) 59 if(du[i]%2==1&&vis[i]) 60 { 61 if(mark[find(i)]==0) 62 mark[find(i)]=1; 63 ans++; 64 } 65 ans/=2; 66 for(int i=1; i<=n; i++) 67 if(mark[i]==0&&vis[i]&&f[i]==i) 68 ans++; 69 printf("%d ",ans); 70 } 71 return 0; 72 }