/*判断是否有欧拉回路，即判断是否为欧拉图 条件1:图连通:用并查集判断 2：不含奇度顶点 */
#include <cstdio> #include <cstring> #define N 1000 using namespace std; int map[N][N]; int n, m; int f[N]; void init() { for (int i = 1; i <= n; i++) f[i] = i; } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void merge(int x, int y) { int t1, t2; t1 = find(x); t2 = find(y); if (t1 != t2) f[t2] = t1; else return; } int main() { while (scanf("%d", &n) != EOF && n) { init(); scanf("%d", &m); int t1, t2; memset(map, 0, sizeof(map)); for (int i = 0; i < m; i++) { scanf("%d%d", &t1, &t2); //输入有t1，t2相等的情况 if (t1 == t2) continue; map[t1][t2] = map[t2][t1] = 1; merge(t1, t2); } int cnt = 0, flag1 = 0;//flag1用来标记是否连通 for (int i = 1; i <= n; i++) { if (f[i] == i) cnt++; } if (cnt == 1) flag1 = 1; //下边判断是否含奇度顶点 int flag2 = 1; for (int i = 1; i <= n; i++) { cnt = 0; for (int j = 1; j <= n; j++) { if (map[i][j]) cnt++; } if (cnt % 2 == 1) { flag2 = 0; break; } } printf("%d\n", flag1 && flag2); } return 0; }上边是自己的ac代码，不过觉得用图存的话比较耗时，第二部分是参考网上思路重写了一遍。
#include <cstdio> #include <cstring> #define N 1000 using namespace std; int n, m; int f[N],degree[N];//记录第i点的度数 void init() { for (int i = 1; i <= n; i++) f[i] = i; } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void merge(int x, int y) { int t1, t2; t1 = find(x); t2 = find(y); if (t1 != t2) f[t2] = t1; else return; } int isEuler() { for (int i = 1; i <= n; i++) if (degree[i] & 1) return 0; return 1; } int isconnect() { int cnt = 0; for (int i = 1; i <= n; i++) { if (f[i] == i) cnt++; } if (cnt == 1) return 1; else return 0; } int main() { while (scanf("%d", &n) != EOF && n) { init(); memset(degree, 0, sizeof(degree)); scanf("%d", &m); int t1, t2; for (int i = 0; i < m; i++) { scanf("%d%d", &t1, &t2); //输入有t1，t2相等的情况 if (t1 == t2) continue; degree[t1]++; degree[t2]++; merge(t1, t2); } printf("%d\n", isEuler() && isconnect()); } return 0; }