哥尼斯堡的“七桥问题”
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/88776995
题目描述：
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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解题思路：
经典的并查集求解。并查集数组pre用来存放每个元素的父结点（初始化为-1），利用并查集搜索来查找老祖宗，当老祖宗仅有一个且奇数点（与其他点有奇数个连接）不存在时，说明这是一个欧拉回路。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 10005
vector<int> v[MAXSIZE]; //用于存放每个点与哪个点连接
int pre[MAXSIZE]; //并查集数组,用于存放每个元素的父节点
int Find(int x) //并查集搜索
{
if(pre[x] == -1) //判断是不是老祖宗
{
return x;
}
else
{
return pre[x] = Find(pre[x]);
}
}
void link(int x,int y) //判断是否联通,不连通就合并
{
if(Find(x)!=Find(y)) //如果不连通，就把它们所在的连通分支合并
{
pre[Find(y)] = Find(x);
}
}
int main()
{
ios::sync_with_stdio(false); //取消cin和stdin的同步
int N,M; //结点数N,边数M
cin >> N >> M;
memset(pre,-1,sizeof(pre)); //并查集数组初始化
int a,b;
for (int i = 1; i <= M; i++) //输入第i条边直接联通的俩个节点的编号
{
cin >> a >> b;
link(a,b); //连接
//把对方分别放进自己的数组
v[a].push_back(b);
v[b].push_back(a);
}
int count = 0; //count用来统计奇数点(与其他点有奇数个连接)
int num = 0; //num用来统计老祖宗个数，老祖宗有且仅有一个说明是连通图
for (int i = 1; i <= N; i++)
{
if (v[i].size() % 2)
{
count++;
}
if (Find(i) == i)
{
num++;
}
}
if (count == 0 && num == 1) //当奇数点不存在且只有一个老祖宗时,是欧拉回路
{
cout << 1 << endl;
}
else
{
cout << 0 << endl;
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-03-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录