题意： 一个老头每天早上散步， 他想知道能不能走过所有的路， 回到出发点， 但不走重复的路。
思路：欧拉回路存在性判断。 连通、 度数都为偶数。度数判断就不说了。 说下连通性的判断吧。
1.并查集
2.DFS， 二维数组G表示u-v路的存在性。走过的点做标记， 没走过一个点vertexCount++； 最后如果vertexCount == vertex则连通。
3.DFS，， 二维数组G表示u-v路的数目。 每走过一次，路的数目–， 走过的路数edgeCount++; 最后如果edgeCount == edge则连通。
题目陷阱： R记edge < 2的时候肯定是不能实现的， 要直接输出。
算法复杂度： 缺省
问题： 我用方法1 AC了， 用2 3就一直WA。 目前还在WA。 现在有点恶心了。 mark下， 下次再来切了。
代码： 并查集
/*并查集判断欧拉回路*/#include <cstdio>#include <cstring>using namespace std;#define MAX_V 210int deg[MAX_V];int father[MAX_V];int vertex;int edge;bool okDeg();int findFathers(int);void unite(int, int);int main(){while (scanf("%d%d", &vertex, &edge) == 2 && (vertex + edge)) {//initmemset(deg, 0, sizeof(deg));for (int i = 0; i < vertex; i++) {father[i] = i;}//enterfor (int i = 0; i < edge; i++) {int u, v;scanf("%d%d", &u, &v);deg[u]++;deg[v]++;unite(u, v);}//mark connectedint set = 0;for (int i = 0; i < vertex; i++) {if (father[i] == i) {set++;}}if (!okDeg() || vertex < 2 || set > 1) {printf("Not Possible\n");}else {printf("Possible\n");}}return 0;}bool okDeg(){for (int i = 0; i < vertex; i++) {if (deg[i] % 2 != 0) {return false;}}return true;}int findFathers(int x){while (x != father[x]) {x = father[x];}return x;}void unite(int x, int y){int pX = findFathers(x);int pY = findFathers(y);if (pX != pY) {father[x] = y;}}
你曾经说，最大的愿望，
