无向连通图，输出每个顶点的度并判断eulerian、semi-eulerian和non-eulerian这3种情况，我们直接记录每个点所连接的点，这样直接得到它的度，然后利用深度优先和visit数组来判断图是否连通，不连通直接是non-eulerian情况，连通的话再判断顶点的度是否都是偶数，是的话就是eulerian情况，不是的话再判断它奇数度的个数是否为2个，也就是偶数比总顶点数少2个，是的话就是就是semi-eulerian情况了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e9; const int maxm = 1e5 + 5; const ll inf = 2147483647; using namespace std; vector<int> v[505]; int visit[505]; void dfs(int x) { if (visit[x] == 0) { visit[x] = 1; for (int i = 0; i < v[x].size(); i++) { dfs(v[x][i]); } } } int main() { int n, m; cin >> n >> m; int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } int sum = 0; cout << v[1].size(); if (v[1].size() % 2 == 0)sum++; for (int i = 2; i <= n; i++) { cout << ' ' << v[i].size(); if (v[i].size() % 2 == 0) sum++; } cout << "n"; dfs(1); int f = 1; for (int i = 1; i <= n; i++) { if (visit[i] == 0) f = 0; } if (!f) { cout << "non-eulerian"; return 0; } if (sum == n) cout << "eulerian"; else if (sum == n - 2) cout << "semi-eulerian"; else cout << "non-eulerian"; return 0; }
0 条评论