欧拉回路的应用&&http://acm.hdu.edu.cn/showproblem.php?pid=3018

题意:给你一个图，问你最少几笔能画完该图，其中孤立的点除外

#include<cstdio>#include<string.h>#include<vector>#include<string>#define N 100005#include<algorithm>#include<iostream>using namespace std;int Father[N];vector<int>a;//记录根节点，其长度为连通分支的个数int in[N];int num[N];//每个连通分支奇度顶点的个数。bool Hash[N];int n,m;void init(){memset(num,0,sizeof(num));for(int i=1;i<=n;++i) Father[i]=i;memset(in,0,sizeof(in));memset(Hash,false,sizeof(Hash));a.clear();}int Find(int x){if(x==Father[x]) return x;return Father[x]=Find(Father[x]);}void Union(int x,int y){ x=Find(x); y=Find(y); if(x!=y) Father[x]=y;}int main(){while(~scanf("%d%d",&n,&m)){init();for(int i=0;i!=m;++i){int a,b;scanf("%d%d",&a,&b);Union(a,b);in[a]++;in[b]++;}int res=0;for(int i=1;i<=n;++i){   int k=Find(i);   if(!Hash[k])   {   Hash[k]=true;   a.push_back(k);   }   if(in[i]&1) num[k]++;  }for(int i=0;i<a.size();++i){int k=a[i];if(!in[k]) continue;if(num[k]==0) res++;else  res+=num[k]/2;} printf("%d\n",res);}return 0;}