洛谷：P2661：信息传递

题目

P2661：信息传递

分析

这道题目我有自己的解法，但是提交后出现了超时、超内存等问题，因为我的解法是属于模拟：每个节点保留当前得到的信息，一旦发现传给的下一个人的信息存在自己的信息库中，那么游戏结束。但是这个算法的开销是很大的。

看了一下题解，发现居然还是一个从并查集出发的解题思路。

先分析样本数据：

2 4 2 3 1

也就是：

• 初始情况下，每个人只有自己的信息，可以用并查集的初始化完成：fa[i]=i。
• （1）告诉2。find(2)=2<>1，没有闭环。fa[1]=2。fa数组变成：2 2 3 4 5。
• （2）告诉4。find(4)=4<>2，没有闭环。fa[2]=4。fa数组变成：2 4 3 4 5。
• （3）告诉2。find(2)=4->find(4)==4<>3，没有闭环。fa[3]=2。fa数组变成：2 4 2 4 5。
• （4）告诉3。find(3)=2->find(2)==4->find(4)=4==4，闭环了。这时跳了3次：3-2-4。更新最小环的长度为3。
• （5）告诉1。find(1)=2->find(2)==4->find(4)=4<>5，没有闭环。fa[5]=1。fa数组变成：2, 4, 2, 4, 1。

核心判断点是：通过find找到的最后祖先是否是本节点。如果是，闭环出现；如果不是，那么更新fa[出发节点]=到达节点。

答案

思考

我问了GPT，它似乎和我一样，对算法的正确性有一些疑惑：因为我总觉得只用一次循环怎么就能完成“几轮”的模拟呢？

我觉得，可能在于，这里的find函数并没有真正地进行路径压缩¹。但我还没有想通为什么如此就可以得到正确答案。