1380

tiger

​ 1.引入经典的七桥问题
哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
​编辑
可否走过这样的七座桥，而且每桥只走过一次？
你怎样证明？
后来大数学家欧拉把它转化成一个几何问题——一笔画问题。
​编辑
我们的大数学家欧拉，找到了它的充要条件
1.奇点的数目不是0个就是2个
奇点：就是度为奇数（如果是有向图就是入读+出度=奇数），反之为偶点
2.概念欧拉路：对于一个图，每条边可以且只能访问一次
欧拉回路：在欧拉图的情况下，最后要回到原点。也就是说欧拉路不一定是欧拉回路，但欧拉回路一定是欧拉路

3.解决方法：
1.dfs第一步：判断图是否连通
第二步：判断奇点个数
很简单，但是使用dfs的话，就需要很多数组，并且用邻接矩阵是最方便的，所以费空间
2.并查集
分为G1和G2两个集合，G1表示已经联通的，G2表示未联通的
利用父亲表示法合并集合效率最高，也是上面那两步
4.例题（1）一笔画问题
题目描述
如果一个无向图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
输入
第一行n，m，0 < n <=20，表示有n个点，m条边，以下m行描述每条边连接的两点。
输出
如果有欧拉路或欧拉回路，输出一条路径即可，顶点之间由空格隔开。
如果没有，输出NO

样例输入1
5 5
1 2
2 3
3 4
4 5
5 1
样例输出1
1 5 4 3 2 1
解法
1.dfs
简单，实用
费空间费时间
2.并查集
效率高，快速，不费时间不费空间
难，费劲
本蒟蒻用的是DFS