Luogu P2921 – 图的遍历

  • 2018-11-28
  • 168
  • 0
  • 0

PROBLEM

https://www.luogu.org/problemnew/show/P2921

ANALYSIS

寻找从每个点出发到访问到已访问节点(将环封闭)用的时间。

起初自己的想到解法应该和 Luogu P2661 – 并查集 差不多,然而在原先题目的思路去思考这个问题有点受限。

 

一种正确的做法:

从所有点开始,尝试对节点染色。

对于遍历的终止条件,有以下两种情况:

  1. 访问到了已经被自己染色的节点;
  2. 访问到了已经被别人染色的节点。

对于 情况1,我们可以直接退出,并且输出当前的时间戳( cnt )。

对于 情况2,又有两种情况:

  1. 访问到了环中节点;
  2. 访问到了环的分支节点(在前往环的路上)。

对于 情况a,输出为 时间戳 + 环的长度

对于 情况b,输出为 时间戳 + 前往环的路的长度 + 环的长度

环的长度,可以在 情况1 退出前, 保存 最后一次搜索的时间戳 – 最后一个访问到的节点的时间戳 作为环的长度。

前往环的路的长度,可以在 情况1 退出前,可以转换为 进入环的时间戳 ,在退出时保存 最后一个访问到的节点的时间戳 作为前往环的路的长度 。

至此,容易想到在 情况2 退出前,保存两者的方法。

SOLUTION

 

REFERENCE

  1. https://www.luogu.org/blog/planetarian/solution-p2921

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

评论

还没有任何评论,你来说两句吧