题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3018 题目大意：给出一个图，问几笔画才能经过所有边。
思路：就是求图的欧拉路径的数量：
对于一个连通子图（连通块） 1：孤立点：不用画 2：是欧拉图，具有欧拉回路：ans++； 3：不是欧拉图，（那么奇数点的数量一定是奇偶数个：离散数学：握手定理）ans=奇数点/2并查集维护连通块(开始以为要dfs染色维护连通块，但是并查集在输入边就维护好了，非常好用啊！)
#include <bits/stdc++.h> using namespace std; int a[100005]; int d[100005]; vector<int> k; bool vis[100005]; int s[100005]; int fd(int x) { if(a[x]<0) { return x; } return a[x]=fd(a[x]); } void L(int x, int y) { x=fd(x), y=fd(y); if(x!=y) { a[x]=y; } } int main() { int n, m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { a[i]=-i; } int u, v; k.clear(); memset(s, 0, sizeof(s)); memset(vis, 0, sizeof(vis)); memset(d, 0, sizeof(d)); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); L(u, v); d[u]++, d[v]++; } for(int i=1;i<=n;i++) { int v=fd(i); if(!vis[v]) { k.push_back(v);//并查集的根v代表这个连通块 vis[v]=1; } if(d[i]%2==1)//度数为奇数 { s[v]++; } } int ans=0; for(int i=0;i<k.size();i++) { int v=k[i]; if(d[v]==0)//孤立点 { continue; } if(s[v]==0)//欧拉回路 { ans++; } else { ans+=s[v]/2; } } printf("%d\n", ans); } return 0; }