并查集
使用y总的并查集的板子
https://lishizheng.blog.csdn.net/article/details/113504280
PAT上ac代码
#include<bits/stdc++.h>
using namespace std;
const int N =510;
int cnt[N];//每个点的度数
int n ,m;
bool g[N][N];//有边
int p[N];
//找根
int find(int x){
if(p[x] != x) p[x] =find(p[x]);
return p[x];
}
int main(){
cin >> n>> m;
for(int i = 1; i<=n; i++) p[i] =i;
while(m--){
int a, b;
cin >> a >> b;
cnt[a]++,cnt[b]++;
p[find(a)] = find(b); //合并集合,如果已经是同一个集合会自动忽略
}
//统计度
int one =0; //统计度为奇数的结点个数
for(int i = 1 ;i <=n; i++){
if( cnt[i] &1 ) one ++;
}
//判连通性
//用set保存根结点个数
set<int> root;
for(int i=1; i<=n; i++)
root.insert(find(i));
int num =root.size();
cout<<cnt[1];
for(int i =2; i<= n; i++) cout<<" "<<cnt[i];
cout<<endl;
if(num==1 &&one == 0) cout<<"Eulerian"<<endl;
else if(num ==1&& one == 2) cout<<"Semi-Eulerian"<<endl;
else cout<<"Non-Eulerian"<<endl;
}