7-4 哥尼斯堡的“七桥问题”
作者:
尘轩
,
2024-11-03 14:33:36
,
所有人可见
,
阅读 7
判断一个图是否有欧拉回路
1. 图必须连通
2. 在无向图中,所有顶点的度数必须为偶数
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int g[N][N];
int d[N];
bool st[N];
void dfs(int v) {
st[v] = true;
for (int i = 1; i <= n; i ++)
if (g[v][i] == 1 && !st[i]) dfs(i);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
d[a] ++;
d[b] ++;
g[a][b] = g[b][a] = 1;
}
dfs(1);
bool flag = true;
// 判断是否连通
for (int i = 1; i <= n; i ++)
if (!st[i]) {
flag = false;
break;
}
// 判断所有顶点的度数是否都是偶数
for (int i = 1; i <= n; i ++) {
if (d[i] % 2 != 0) {
flag = false;
break;
}
}
if (flag) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}