准确的说,就是发现可以用普通的并查集的理由不对。
先说说我个人的理解:
首先,这类题目的通法就是统计缩点后入度为 0 的点。一般来说,这类题根本不能用普通的并查集做,能用是因为这道题不同于其他同类题的性质,才导致这道题只用并查集就能搞定。
因为题目中是第 i 个罐子的钥匙在第 xi 个罐子里,如果说是 tarjan 的思路,就是存在一条从 xi 到 i 的有向边,也就是说 i 有一个入度,因为每个 i 只会出现一次,所以也就是说每个点的入度只可能是 1,因此每个连通块必然有且仅有一个环,并且这个环还必须在最顶端,也就是缩点后是这个连通块唯一一个入度为 0 的点,也就是必须砸这个环内的一个罐子。就是这个性质,让这道题可以使用并查集,但是我没有看见一篇题解写了这个性质,有很接近的,但也是错误的。
一篇题解说出现环形,就要砸一个罐子,这显然只有在这一道题目下成立,如果是其他题目,那么可能环缩点后入度不是 0,题解又不说为什么,很容易误导初学者。
又比如,有题解说,连通块就要砸一个罐子,同样只在这一道题有效,因为其他题可能存在一个连通块有多个入度为 0 的点,就不止砸一个罐子。
还有题解说的很模糊,有一个打开了,其他就都打开了,同样的,如果你打开的不是入度为 0 的点(缩点后),那么,就无法全部打开。
还有一篇题解最接近:
由于每个节点有且仅有一个入度,所以一个联通块不可能有多个环(两个环无法连在一起),即每个联通块有且仅有一个环(包括自环),而只有环才需要打破箱子
但是也没说清楚,不是只有环才需要打破箱子,是环必定出现在最前面。
还有好多连思路都不写,建议撤下所有思路有误的题解