1126. Eulerian Path (25)

题目已经说证明了，那么按他的意思来就好了，注意判断图是否连通

#include<iostream> #include<vector> using namespace std; int N, M; int arc[505][505] = {}; int degree[505] = {}; int visited[505] = {}; void dfs(int index) { for (int t = 1;t <= N;t++) if (!visited[t] && arc[index][t] != 0) { visited[t] = 1; dfs(t); } } int main() { cin >> N >> M; while (M--) { int a, b; cin >> a >> b; degree[a]++;degree[b]++; arc[a][b] = arc[b][a] = 1; } int oddnum = 0; int cnt = 0; cout << degree[1]; if (degree[1] % 2) oddnum++; for (int t = 2;t <= N;t++) { cout << " " << degree[t]; if (degree[t] % 2) oddnum++; } cout << endl; for (int t = 1;t <= N;t++) if (!visited[t]) { if (++cnt == 2) break; visited[t] = 1; dfs(t); } if (cnt == 2) { cout << "Non-Eulerian" << endl; return 0; } if (oddnum == 0) cout << "Eulerian" << endl; else if (oddnum == 2) cout << "Semi-Eulerian" << endl; else cout << "Non-Eulerian" << endl; }