【HDU 1811】 Rank of Treris(拓扑排序+并查集)

26
Sep

【HDU 1811】 Rank of Treris(拓扑排序+并查集)

这道题应该算思路有点新颖的了,在进行排序之前需要用并查集先进行一个“缩点“的过程,然后才能进行拓扑排序并且要仔细考虑如何处理缩点后的边的处理。说起来这题窝错了好几次,后来发现是并查集写错了,从学长的模板里贴了个并查集才过,也是OTZ,数据结构还是菜啊。。。。

题面描述
给定一张图,包含两种关系:一个是两点之间有边相连,另一个是一种”等价“关系,即将两点视为同一点,共享所有的边,求问这张图是否可以被唯一拓扑排序(等价关系视为不存在歧义),要求三种结果:可以被排序;存在环;图不完全。在图不完全又存在环时,输出它存在环。
解题思路
这道题第一感觉和POJ 1094很像(可以在我的博客中找到这题的题解),要求三种关系,也是优先判环,所以思路上可以借鉴。但是这道题的难点在于,有一个等价关系的定义我们要想办法将两个等价点的边处理到一个点上,于是想到用并查集+路径压缩将所有等价的点缩到一个点上,然后再进行正常拓扑排序的过程就可以了。
代码编写
这道题的难点在于处理等价点的关系,而等价点之间需要传递的是边的关系,那么我们不妨将路径压缩后每个点的father作为其映射值(因为并查集中所有统一集合的点都统一有一个father,孤立点的father是它自己),在建图的时候把每个节点转换到其映射值再操作,同时维护每个father实际代表的节点数量。至于判断三种情况的过程,类似POJ 1094的返回值写就可以了。

AC代码
https://paste.ubuntu.com/25616351/

由于个人水平有限,上述文字可能存在错误,如有问题,欢迎指正和讨论!

添加新评论