注意坑点:要判断是否是连通图
使用并查集来判断是否是连通图
C++ 代码
// 坑点:要判断是否是连通图
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 510;
int cnt[N], p[N];
int find_top(int x) {
if(x != p[x])
p[x] = find_top(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = 0;i < m;i ++) {
int a, b;
cin >> a >> b;
cnt[a] ++, cnt[b] ++;
p[find_top(a)] = find_top(b);
}
int ck = 0;
bool flag = true;
int head = find_top(1);
for(int i = 1;i <= n;i ++) {
if(find_top(i) != head) flag = false;
cout << cnt[i];
if(i != n) cout << " ";
ck += cnt[i] % 2;
}
cout << endl;
if(!flag || (ck != 0 && ck != 2)) cout << "Non-Eulerian";
else if(!ck) cout << "Eulerian";
else if(ck == 2) cout << "Semi-Eulerian";
return 0;
}