526互联

CF827D Best Edge Weight 题解

发布时间 2023-11-03 10:24:26作者: FOX_konata

Problem - 1867D - Codeforces

Cyclic Operations - 洛谷

  • 差一点就想出来了

  • 首先 \(b_i\) 构建出来的肯定是一个章鱼森林，而且手玩一下样例就会发现我们每次要找到一个大小为 \(K\) 的环后让里面的点重新指向，一直重复这些操作直到所有点都被找到。

  • 我们考虑对于一个环，我们要如何对里面的点重定向才能让他延申出去的每个森林都可以组成一个大小为 \(K\) 的环

  • imagepng

  • 如图，我们发现可以重定向红色边来组成一个新的大小为 \(K\) 的环，并一直重复这样的操作，显然是合法的。

  • 因此原问题就变成了判断这个章鱼森林里每个环大小是否为 \(K\) 。你可以使用 dfs Or tarjan 。但有一种更好的解决方式：我们通过拓扑排序把里面所有延申出去的"触手"给标记上，显然这个图就只剩若干个环了，剩下的就非常 simple 了

  • 最终复杂度 \(O(n)\)