水题。无向图欧拉通路的判定。用并查集判定是不是连通图！
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn = 1000 + 10; int tott[maxn]; int father[maxn]; int find(int x) { if (x != father[x]) father[x] = find(father[x]); return father[x]; } int main() { int T; scanf("%d", &T); while (T--) { int i, n, m, u, v; scanf("%d%d", &n, &m); for (i = 0; i <= n; i++) father[i] = i; memset(tott, 0, sizeof(tott)); for (i = 0; i < m; i++) { scanf("%d%d", &u, &v); int fu = find(u); int fv = find(v); if (fu != fv) father[fu] = fv; tott[u]++; tott[v]++; } int ji = 0, ou = 0; for (i = 1; i <= n; i++) { if (tott[i] == 0) continue; if (tott[i] % 2 == 0) ou++; else ji++; } int jieguo = 0; int th = find(1); for (i = 2; i <= n; i++) { int tg = find(i); if (tg != th) break; } if (i == n + 1) jieguo = 1; if (jieguo == 1) { if (ji == 0 || ji == 2) jieguo = 1; else jieguo = 0; } if (jieguo == 1) printf("Yes "); else printf("No "); } return 0; }