欧拉回路的应用&&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;}
