【题目来源】https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId859https://pintia.cn/problem-sets/15/exam/problems/type/7【题目描述】哥尼斯堡是位于普累格河上的一座城市它包含两个岛屿及连接它们的七座桥如下图所示。可否走过这样的七座桥而且每桥只走过一次瑞士数学家欧拉(Leonhard Euler1707—1783)最终解决了这个问题并由此创立了拓扑学。这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面可画过图中每条边仅一次且可以回到起点的一条回路。现给定一个无向图问是否存在欧拉回路【输入格式】输入第一行给出两个正整数分别是节点数 n 1≤n≤1000和边数 m随后的 m 行对应 m 条边每行给出一对正整数分别是该条边直接连通的两个节点的编号节点从1到 n 编号。【输出格式】若欧拉回路存在则输出 1否则输出 0。【输入样例一】6 101 22 33 14 55 66 41 41 63 43 6​​​​​​​【输出样例一】1【输入样例二】5 81 21 32 32 42 55 35 43 4【输出样例二】0【数据范围】1≤n≤1000​​​​​​​【算法分析】● 欧拉路径与欧拉回路定义图中经过所有边恰好一次的路径称为欧拉路径也就是一笔画。如果此路径的起点和终点相同则称其为欧拉回路。注意若存在欧拉回路则一定存在欧拉路径。● 欧拉路径判定1有向图欧拉路径图中恰好存在 1 个结点的出度比入度多 1这个结点即为起点 S1 个结点的入度比出度多 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 N1e35; int g[N][N]; int st[N],du[N]; int n,m; void dfs(int u) { st[u]1; for(int i1; in; i) { if(st[i]0 g[u][i]!0) dfs(i); } } int main() { cinnm; int a,b; while(m--) { cinab; g[a][b]g[b][a]1; du[a]; du[b]; } for(int i1; in; i) { if(du[i]%2!0) { cout0; return 0; } } dfs(1); for(int i1; in; i) { if(st[i]0) { cout0; return 0; } } cout1; 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/160888941https://blog.csdn.net/hnjzsyjyj/article/details/149031663https://blog.csdn.net/hnjzsyjyj/article/details/140747624https://blog.csdn.net/qq_62658309/article/details/127845829