题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3018
题意：给你一个图，每条路只能走一次。问至少要多少个人才能遍历所有的点和所有的边。
这是之前没有接触过的知识点。设计欧拉图，不理解直接记住就好啦。
欧拉图：若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。
若该路径是一个圈，则称为欧拉(Euler)回路。具有欧拉回路的图称为欧拉图。
具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图。
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。
思路：队伍数=奇度数/2+欧拉回路数(欧拉回路中所有顶点的度数均为奇数，且是联通图) 求的是总和。
用并查集找连通图，用不定长数组存连通图。
代码：
#include<iostream> #include<cstdio> #include<iostream> #include<cstring> #include<vector> using namespace std; #define ll long long const int INF=0x3f3f3f3f; const int maxn=1e5+5; int n,m; vector<int>V; int p[maxn],odd[maxn],vit[maxn],d[maxn]; void init() { V.clear(); for(int i=1;i<=n;i++) p[i]=i; memset(odd,0,sizeof(odd)); memset(vit,0,sizeof(vit)); memset(d,0,sizeof(d)); } int Find(int x) { if(x!=p[x]) p[x]=Find(p[x]); return p[x]; } int main() { while(scanf("%d%d",&n,&m)==2) { init(); for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); d[a]++,d[b]++; int pa=Find(a); int pb=Find(b); if(pa!=pb) p[pb]=pa; } for(int i=1;i<=n;i++) { int k=Find(i); if(vit[k]==0) { V.push_back(k); vit[k]=1; } if(d[i]%2==1) odd[k]++; } int ans=0; for(int i=0;i<V.size();i++) { int v=V[i]; if(d[v]==0) continue; if(odd[v]==0) ans++; else ans+=odd[v]/2; } printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/a-clown/p/6306137.html