P2661 [NOIP2015 提高组] 信息传递 分析

· · 个人记录

题意就是求一个图中的最小环。但本题的边有很大的特殊性，因此可以用并查集完成。

有怎样的特殊性？

—— 本题中一个点最多有两条边相连，一条出边一条入边。所以可以用并查集解决。

并查集可以轻松判断是否形成环。但是要怎样计算环的长度？

实际上当一个点 A 在这个图（并查集）中形成环的时候，这个环的长度就是它到祖先的距离， find 过程递归的次数。