以前是想到过类似的算法的，但这题并没有突破成功，后来发现做法改一改就好了。很好的图论题。

先考虑 怎么做，就是枚举每个点，维护其能到达的连通块，用个队列进行广搜。对每种颜色维护一个 vector，对于在连通块边界上但暂时还走不过去的点，将其加入对应颜色的 vector 中。广搜时将队首出队后，先把所有该点对应颜色 vector 中的点入队后，再去看它的相邻点。这样我们就可以求出每个点能到达几个点，单次时间复杂度 。

上述过程主要输在各个点之间的信息没有互相利用，对每个点的求解完全独立。况且我们只需要知道 最小的位置，并不需要求出每个 。于是考虑有什么信息能让我们在 之间比大小。

对于一个点 ，如果其没有颜色为 的邻边，显然其 ，否则。如果 之间的边颜色为 。那 肯定大于等于 。

于是就有一个想法，建一张新图，对于一条边 ，如果 就在新图中连一条有向边 。连完之后的无出边点用来更新答案。然后把 SCC 缩成一个新点，重新建边。此时每个点对应原图中一个连通块，其大小就不一定是 ，其中包含的钥匙也不一定只有一种，把上文的 改成 即可。一直重复上述过程。

但这种做法最坏需要重复 轮，跟原来的暴力没区别。

这一定是我们信息用的不够完全。注意到上述做法没有充分利用一条边的比大小功能。究其原因是我们对”连通块“ 的限制太严格，要求其一定得是 SCC，导致连通块的合并机会其实很少。考虑拓展连通块的定义，我们只需要其中存在一个点 ，使得块中所有点都能到达 即可。 不一定要能到达连通块中的所有点。

此时原图仍然被分成若干个连通块，每个连通块都有一个代表点 。考虑仍然通过”找出边“ 的方式合并这些连通块。对于一个连通块，从其对应的 开始搜索，直到走到一个不在当前块中的点 。那么我们可以就可以把 中的所有点合并到 上。如果不存在这样的点，那么 设 BFS 过程中所走到的点集为 ，容易发现 中每个点可以到达的点集都恰好是 。用 更新答案即可。同样执行若干轮这种合并过程，就能得到最终解。

时间复杂度方面。因为每个连通块每轮要么没有出边，此时其会被删去，后面不考虑它，要么有条出边，能够将两个连通块合并起来，所以合并后连通块个数至少减少一半，因此总共只会执行 轮合并过程，每轮每个连通块 BFS 的复杂度之和是 的。总时间复杂度为 。

代码：https://loj.ac/s/2003753