杭州高端定制网站/seo优化多少钱

一、题目

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？输入格式:
输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。输出格式:
若欧拉回路存在则输出1，否则输出0。输入样例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6
输出样例1:
1
输入样例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4
输出样例2:
0

二、相关知识

1.考察欧拉回路问题
欧拉回路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，
如果存在一条回路经过G每条边有且仅有一次有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。2.并查集
使用并查集解决此问题。
通过并查集可以得知该节点是否度数为0，即是否是单独的一个点或者连通块
[并查集知识](https://zhuanlan.zhihu.com/p/93647900/)

三、代码

（同一学校请勿直接扮演。。。😰害怕）

//七桥问题
//欧拉回路、并查集
#include<iostream>
using namespace std;
int dushu[1010];//节点度数记录 
int fa[1010];//并查集
int find(int x)
{//将父节点设置为根节点 return x==fa[x]?x:(fa[x]=find(fa[x]));}
void merge(int x,int y)//合并，将序号小的设置为序号大的根节点 
{int fx=find(x);int fy=find(y);//寻找两个根节点 if(fx>fy)fa[fx]=fy;elsefa[fy]=fx;} int main(){for(int i=0;i<1010;i++)fa[i]=i;//初始化操作，一般将父节点设置为本身 int n,m;cin>>n>>m;for(int i=0;i<m;i++){int x1,x2;cin>>x1>>x2;merge(x1,x2);//合并，设置父节点 dushu[x1]++;dushu[x2]++; }int flag=1;//设置判断标志int sum=0;//连通块个数for(int i=1;i<=n;i++){//无向连通图，且所有节点度数为偶数，则存在欧拉回路 if(dushu[i]%2!=0)flag=0;//度数为奇数，不连通if(i==fa[i])sum++;//判断度数为0的点（父节点是其本身，证明度数为0） }if(sum!=1)flag=0;if(flag==1) cout<<"1";if(flag==0) cout<<"0"; return 0; } 

程序是蓝色的诗