poj并查集专练

并查集小结 并查集大体分为三个：普通的并查集，带种类的并查集，扩展的并查集（主要是必须指定合并时的父子关系，或者统计一些数据，比如此集合内的元素数目。） POJ-1182 经典的种类并查集 POJ-1308 用并查集来判断一棵树。。注意空树也是树。 POJ-1611 裸地水并查集 POJ-1703 种类并查集 POJ-1988 看上去似乎和种类并查集无关，但其实仔细想想，就是种类并查集。。。 只不过是种类数目无穷大，通过合并，可以确定两个物品之间的种类差（即高度差） POJ-2236 裸地并查集，小加一点计算几何 POJ-2492 裸地种类并查集 POJ-2524 又是裸地并查集 POJ-1456 常规思想是贪心+堆优化，用并查集确实很奇妙。 POJ-1733 种类并查集，先要离散化一下，不影响结果。 HDU-3038 上一道题的扩展，也是种类并查集，种类无穷大。 POJ-1417 种类并查集，然后需要背包原理来判断是否能唯一确定“好人”那一堆 POJ-2912 baidu的题 ZOJ-3261 NUAA-1087 逆向使用并查集就可以了。 POJ-1861 POJ-2560 Kruskal并查集