【题目来源】
https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId=859
https://pintia.cn/problem-sets/15/exam/problems/type/7
【题目描述】
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
【输入格式】
输入第一行给出两个正整数，分别是节点数 n （1≤n≤1000）和边数 m；随后的 m 行对应 m 条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到 n 编号）。
【输出格式】
若欧拉回路存在则输出 1，否则输出 0。
【输入样例一】
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6
【输出样例一】
1
【输入样例二】
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4
【输出样例二】
0
【数据范围】
1≤n≤1000
【算法分析】
● 欧拉路径与欧拉回路定义
图中经过所有边恰好一次的路径称为欧拉路径（也就是一笔画）。
如果此路径的起点和终点相同，则称其为欧拉回路。
注意：若存在欧拉回路，则一定存在欧拉路径。
● 欧拉路径判定
（1）有向图欧拉路径：图中恰好存在 1 个结点的出度比入度多 1（这个结点即为起点 S），1 个结点的入度比出度多 1（这个结点即为终点 T），其余结点的出度=入度。
（2）有向图欧拉回路：所有结点的入度=出度（起点 S 和终点 T 可以为任意点）。
（3）无向图欧拉路径：图中恰好存在 2 个结点的度是奇数，其余结点的度为偶数，这两个度为奇数的结点即为欧拉路径的起点 S 和终点 T。
（4）无向图欧拉回路：所有结点的度都是偶数（起点 S 和终点 T 可以为任意结点）。
● 这个问题可以转化为计算图中连通分量个数和奇度数顶点个数。
如果一个连通分量中所有顶点度数为偶数，则该分量存在欧拉回路，可以一笔画成。
如果一个连通分量中有 k 个奇度数顶点，则需要 k/2 笔才能画完（k 为偶数，根据图论握手定理）。
【算法代码】
#include <bits/stdc++.h> using namespace std; const int N=1e3+5; int g[N][N]; int st[N],du[N]; int n,m; void dfs(int u) { st[u]=1; for(int i=1; i<=n; i++) { if(st[i]==0 && g[u][i]!=0) dfs(i); } } int main() { cin>>n>>m; int a,b; while(m--) { cin>>a>>b; g[a][b]=g[b][a]=1; du[a]++; du[b]++; } for(int i=1; i<=n; i++) { if(du[i]%2!=0) { cout<<0; return 0; } } dfs(1); for(int i=1; i<=n; i++) { if(st[i]==0) { cout<<0; return 0; } } cout<<1; return 0; } /* in: 5 8 1 2 1 3 2 3 2 4 2 5 5 3 5 4 3 4 out: 0 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160888941
https://blog.csdn.net/hnjzsyjyj/article/details/149031663
https://blog.csdn.net/hnjzsyjyj/article/details/140747624
https://blog.csdn.net/qq_62658309/article/details/127845829
