7-32 哥尼斯堡的“七桥问题” (25 分)

亦凉 2023-01-15 11:24 16阅读 0赞

**判断欧拉回路是否存在的方法**

**有向图：图连通，所有的顶点出度=入度。  
无向图：图连通，所有顶点都是偶数度。**

推荐一篇博文，感觉很好---->[欧拉回路基本概念+判断+求解][Link 1]

--------------------

**首先判断图是否联通，如果不连通，直接输出0，程序结束；如果连通，继续进行下一步，判断每个顶点的度数是否为偶数，如果全为偶数，输出1，否则输出0**

#include <iostream>
    #include <cstring>
    using namespace std;
    int n, m;
    int mp[1005][1005], f[1005];
    int find(int x) {
        
    	if(x == f[x]) return x;
    	return f[x] = find(f[x]);
    }
    int main() {
        
    	cin >> n >> m;
    	memset(mp, 0, sizeof(mp));
    	for(int i = 0; i <= n; i++) {
        
    		f[i] = i;
    	}
    	for(int i = 0; i < m; i++) {
        
    		int a, b;
    		cin >> a >> b;
    		mp[a][b] = mp[b][a] = 1;
    		int f1 = find(a), f2 = find(b);
    		if(f1 != f2) {
        
    			f[f1] = f2;
    		}
    	}
    	int cnt = 0;
    	for(int i = 1; i <= n; i++) {
        
    		if(f[i] == i) cnt++;
    	}
    	if(cnt > 1) {
        
    		cout << "0";
    		return 0;
    	}
    	int flag = 0, num;
    	for(int i = 1; i <= n; i++) {
        
    		num = 0;
    		for(int j = 1; j <= n; j++) {
        
    			if(mp[i][j] == 1) num++;
    		}
    		if(num%2){
        
    			flag = 1;
    			break;
    		}
    	}
    	if(flag) cout << "0";
    	else cout << "1";
    }

**题目描述**  
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。  
![在这里插入图片描述][20210422143751279.png]  
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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:**

**输入样例2:**

5 8
    1 2
    1 3
    2 3
    2 4
    2 5
    5 3
    5 4
    3 4

**输出样例2:**

[Link 1]: https://www.cnblogs.com/wkfvawl/p/9626163.html
[20210422143751279.png]: /images/20221022/0ec4560380aa4197b2f225a0c13363ce.png