输入格式: 输入第一行给出两个正整数,分别是节点数N (1≤N≤1000)和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。 输出格式: 若欧拉回路存在则输出1,否则输出0。c实现
时间: 2024-02-18 18:05:27 浏览: 19
以下是C++的实现代码,使用邻接表存储有向图,并使用深度优先搜索确定是否存在欧拉回路:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
void dfs(int u, vector<bool>& visited, int& cnt) {
visited[u] = true;
cnt++;
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v, visited, cnt);
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 邻接表存储有向图
graph.resize(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
}
// 使用深度优先搜索判断是否存在欧拉回路
vector<bool> visited(n + 1);
for (int i = 1; i <= n; i++) {
int cnt = 0;
dfs(i, visited, cnt);
if (cnt != n) {
cout << 0 << endl;
return 0;
}
}
cout << 1 << endl;
return 0;
}
```
代码思路:
1. 读入顶点数n和边数m;
2. 创建空的邻接表graph;
3. 读入每条边的信息,将其添加到对应的起点的邻接表中;
4. 使用深度优先搜索遍历每个顶点,判断从该顶点出发是否能够遍历到所有顶点,如果能,则存在欧拉回路;
5. 如果所有顶点都能够满足遍历到,则存在欧拉回路;否则不存在欧拉回路。