6.15 七桥问题，欧拉回路

欧拉回路就是，用一条线，走过所有的路，而且不重复，这种问题使用了并查集

并查集分为两个部分：

查找：

1.初始化，将每个节点都初始化成一颗树

find（）：根据给的边，找到他们的根节点，并更新

union（）：把根节点不一样的连成一颗树，实现几棵树变成一棵树

并查集的作用：

在于判断所有的节点是不是属于同一个根节点，如果都属于1个根节点，就是一个联通分量，那么是联通的，要不然，就不是

除此之外，还用了度，如果度是偶数，则这个节点不是孤立的，，是被经过的，如果是奇数，则说明存在一条孤立的边，无法被访问；

为什么cnt=1，说明只有一棵树，就代表是联通的：

只有一颗树，那么每个节点之间都有路径，就是联通的

7-12 哥尼斯堡的“七桥问题“

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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

#include<iostream>
using namespace std;
const int N = 1001;
int n, m;
int root[N];
int grade[N];
int find(int x) {
	if (x == root[x]) return x;
		return root[x]= find(root[x]);//这地方出错是因为忘了给root[x]赋值了
}
void merge(int x, int y) {
	int X = find(x);//这个地方出错，因为find是用来查找根节点的，不能直接让x=root[x]
                     //因为这可能并不是最终的查找结果
	int Y = find(y);
	if (X != Y) {
		root[X] = Y;
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		root[i] = i;
	}
	while (m--) {
		int a, b;
		cin >> a >> b;
		if (find(a) != find(b)) {   //需要先判断a，b不是一个根节点的，再合并
			merge(a, b);
		}
		grade[a]++, grade[b]++;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (find(i)==i)cnt++;
	}
	if (cnt == 1) {
		bool q = 1;
		for (int i = 1; i <= n; i++) {
			if (grade[i] % 2 != 0) {
				q = 0;
				break;
			}
		}
		if (q) cout << "1";
		else cout << "0";
	}
	else cout << "0";
}