大意略。
思路:无向图的欧拉回路。
条件:1、连通图 2、所有点的度为偶数。
还有需要注意的地方。
这组测试数据:
3 2
0 1
1 0
我测试了一下,可以输出Possible也可以输出Not Possible都可以过。
如果孤立的点不算一个连通分量的话,那么则输出Possible,如果算的话,则输出Not Possible,两者均可。
我的代码把它们单独看做一个连通分量。
#include <iostream> #include <cstdlib> #include <cstring> #include <string> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 210; int n, m; int degree[maxn]; int p[maxn]; void UFset() { for(int i = 0; i < n; i++) p[i] = i; } int find(int x) { return x == p[x]? x : p[x] = find(p[x]); } void Union(int a, int b) { int x = find(a), y = find(b); if(x == y) return ; p[x] = y; } void init() { UFset(); memset(degree, 0, sizeof(degree)); //忘记初始化了 } void read_case() { init(); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); degree[u]++, degree[v]++; Union(u, v); } } int check() { int scnt = 0; for(int i = 0; i < n; i++) if(p[i] == i) scnt++; for(int i = 0; i < n; i++) { if(degree[i] & 1) return 0; } return scnt == 1; } void solve() { read_case(); if(check()) printf("Possible\n"); else printf("Not Possible\n"); } int main() { while(~scanf("%d%d", &n, &m)) { solve(); } return 0; } /* 测试数据 3 2 0 1 1 0 2 2 1 0 1 0 4 4 0 1 1 0 2 3 3 2 5 6 0 1 1 0 2 3 2 3 0 2 2 0 4 6 1 2 2 1 2 3 2 3 3 1 1 3 2 0 Not Possible/Possible Possible Possible Not Possible Not Possible Not Possible */