这题，欧拉回路的应用，只是比较麻烦。
题目的意思是，一群蚂蚁，想要走遍给定的每一条边，但是，图不连通或者不存在欧拉回路的不可能走完，所以可以将人分组，求解最少的分组的数目。
解题的主要思路是：
1.将各点进行合并，使用并查集。
2.遍历并查集，查找各个连通图的奇数度的个数。
3.如果该连通图的奇数点为0，只需一笔。如果不是，就需要奇数点的数目 / 2。
还有一点需要注意的是，，单个点应该无视他，题目有讲到。
题目有点坑，输入那里还有样例那里每一个测试样例有一个空行。可是实际上不需要空格，是的，不需要，坑了我两个PE。
下面是AC的代码，有详细注释：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int MAX = 100005;bool vis[MAX];//判断该顶点是否出现过int par[MAX], degree[MAX], M, E; //par为并查集，degree为各个顶点的度。int temp[MAX];//各个连通图的奇数点个数int finds(int x)//并查集的查找函数{int r = x;while(r != par[r])r = par[r];int i = x, j;while(i != r)//压缩路径{j = par[i];par[i] = r;i = j;}return r;}void join(int x, int y)//并查集合并函数{int fx = finds(x);int fy = finds(y);if(fx != fy)par[fy] = fx;}int main(){int a, b, i;bool flag = false;while(scanf("%d%d", &M, &E) != EOF){memset(degree, 0, sizeof(degree));//初始化各个数组memset(temp, -1, sizeof(temp));memset(vis, false, sizeof(vis));for(i = 0; i <= M; i++)par[i] = i;for(i = 0; i < E; i++){scanf("%d%d", &a, &b);if(a == b)//顶点相同，直接跳过continue;if(a > b){a = a ^ b;b = b ^ a;a = a ^ b;}join(a, b);//合并两个顶点degree[a]++; vis[a] = true;//该点度+1，标记为该点存在degree[b]++; vis[b] = true;}int ans = 0;for(i = 1; i <= M; i++)//遍历每一个顶点{int j = finds(i);//查找属于哪个连通图if(temp[j] == -1)//该连通图是新的，也就是之前没查找到的，temp[j] = 0;//初始化奇数点为0。if(degree[i] % 2)//如果该点的度为奇数temp[j]++;//奇数点+1；}for(i = 1; i <= M; i++)//遍历每一个顶点{if(temp[i] > 0 && vis[i])//奇数点 > 0 ，且该点出现过ans += temp[i] / 2;//分组数加上奇数点 / 2；else if(temp[i] == 0 && vis[i])//奇数点为0，该点出现过ans++;//分组数 + 1；}cout << ans << endl;}return 0;}
从哪里跌倒就会从哪里爬起来,让我们一起努力吧
