个人认为这道题大部分题解思路不严谨
查看原帖
个人认为这道题大部分题解思路不严谨
86507
One_JuRuo楼主2023/9/13 08:56

准确的说,就是发现可以用普通的并查集的理由不对。

先说说我个人的理解:

首先,这类题目的通法就是统计缩点后入度为 00 的点。一般来说,这类题根本不能用普通的并查集做,能用是因为这道题不同于其他同类题的性质,才导致这道题只用并查集就能搞定。

因为题目中是第 ii 个罐子的钥匙在第 xix_i 个罐子里,如果说是 tarjan 的思路,就是存在一条从 xix_i 到 ii 的有向边,也就是说 ii 有一个入度,因为每个 ii 只会出现一次,所以也就是说每个点的入度只可能是 11,因此每个连通块必然有且仅有一个环,并且这个环还必须在最顶端,也就是缩点后是这个连通块唯一一个入度为 00 的点,也就是必须砸这个环内的一个罐子。就是这个性质,让这道题可以使用并查集,但是我没有看见一篇题解写了这个性质,有很接近的,但也是错误的。

一篇题解说出现环形,就要砸一个罐子,这显然只有在这一道题目下成立,如果是其他题目,那么可能环缩点后入度不是 00,题解又不说为什么,很容易误导初学者。

又比如,有题解说,连通块就要砸一个罐子,同样只在这一道题有效,因为其他题可能存在一个连通块有多个入度为 00 的点,就不止砸一个罐子。

还有题解说的很模糊,有一个打开了,其他就都打开了,同样的,如果你打开的不是入度为 00 的点(缩点后),那么,就无法全部打开。

还有一篇题解最接近:

由于每个节点有且仅有一个入度,所以一个联通块不可能有多个环(两个环无法连在一起),即每个联通块有且仅有一个环(包括自环),而只有环才需要打破箱子

但是也没说清楚,不是只有环才需要打破箱子,是环必定出现在最前面。

还有好多连思路都不写,建议撤下所有思路有误的题解

2023/9/13 08:56
加载中...