xindoo is
always here

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的题,AC了,不过有点乱,有时间【【【再看看】】】


ZOJ-3261   NUAA-1087


逆向使用并查集就可以了。。。


POJ-1861 
POJ-2560


Kruskal并查集



 


打赏
未经允许不得转载:XINDOO » poj 并查集小结
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏