判断是否存在欧拉路径(无向图)
存在欧拉路径: 奇数度的点的个数为0或2
存在欧拉回路:奇数度的点的个数为0
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 510;
int d[maxn];
int w[maxn][maxn];
bool st[maxn];
int n, m;
int dfs(int u)
{
st[u] = true;
int cnt = 1;
for(int i = 1; i <= n; i ++){
if(!st[i] && w[u][i]){
cnt += dfs(i);
}
}
return cnt;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++){
int a, b; cin >> a >> b;
d[a] ++, d[b] ++;
w[a][b] = w[b][a] = 1;
}
int cnt = dfs(1);
for(int i = 1; i <= n; i ++){
if(i != 1) cout << " ";
cout << d[i];
}
cout << endl;
if(cnt == n)
{
int s = 0;
for(int i = 1; i <= n; i ++){
if(d[i] % 2) s ++;
}
if(s == 0) cout << "Eulerian" << endl;
else if(s == 2) cout << "Semi-Eulerian" << endl;
else cout << "Non-Eulerian" << endl;
}else cout << "Non-Eulerian" << endl;
return 0;
}