题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1116 离散数学的知识，囧，这一块没怎么学，基础很薄弱啊。 不过对于欧拉回路/通路的结论，倒是不难推出。 欧拉通路：除首尾结点外，其余结点入度等于出度，起点出度减入度等于1，终点入度减出度等于1 欧拉回路：所有结点的入度都等于出度 思路：将每一个单词的首尾字母当做结点，首尾字母间连线，判断最后形成的有向图能否形成欧拉通路/回路，用并查集。
并查集(Disjoint Set) 起因：在某些应用中，要将n个不同的元素分成一组不相交的集合。 第21.1节 不相交集合的链表表示有些不太明白，有达人讲解或贡献出自己的学习笔记？？？？ 启发式策略是什么？—>我对这个概念一直很好奇？？？但是一直找不到好的文章和解释，看到我文章的朋友，求推荐，谢谢。 21.3节 不相交集合森林 这个曾经写过一个模板，书看了后，基本都可以写出来吧，依葫芦画瓢，代码模板链接： http://www.wutianqi.com/?p=1066 至于两种启发式策略，来分别说下其作用： ①.按秩合并(union by rank)，把较少结点的树的根合并到较多结点的树的跟，这样是为了尽量使树的高度减小，因此，可以优化Find_Set(x)。（看Find_Set()函数的代码~~） ②.路径压缩(path compression)，使查找路径上的每个结点都指向根节点，路径压缩并不改变结点的秩，而且这样也同样优化了Find_Set(x)。 完毕！
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2208 有人说用位状态压缩做，等会去试试。 我首先想到的时强连通分支，算出分支数，如果小于气球数，则OK，这里用了并查集的思想。 AC代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 [...]
题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1213 这题粗略一看好熟悉，原来和 POJ 2524 Ubiquitous Religions 一模一样，就是输出时不用输出Case情况计数。Orz 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 [...]
题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=1856 并查集~~~ 这题有问题，在对待n==0的情况时，标程是输出为1，而按理应该是0~~~ 经果冻布丁提醒，题目是对的，有这么一句话：or there is only one boy left 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 [...]