考虑把\(i\to k_i\)连边,这样形成若干个环。考虑断环为链并且把链复制一份接到后面。
考虑求出从一个点集开始拓展能够到达的点集\(S1_i\)。显然\(S1_i\)在环上是连续的,设\(r_i\)表示第\(i\)个节点拓展能得到的右端点。
考虑每个节点\(i\)所在强连通分量的点集合\(S2\)。可以证明\(S2\)在环上也是连续的。
显然如果一个节点\(x\)能够到达\(y\),则\(x\)的\(S1\)包含\(y\)的\(S1\)。
于是可以考虑如下过程:考虑如果我们求出了环上第\(i\to 2*n\)个节点的\(S1\),如何求出环上的第\(i-1\)个节点的\(S1\)集合。
显然环上第\(i-1\)个节点要和第\(i\)个节点有连边第\(i-1\)个节点才能拓展到第\(i\)个节点,此时可以把第\(i-1\)个节点的\(r\)设置为第\(i\)个节点的\(r\)。
考虑用并查集维护一个节点所在的强连通分量,并且根节点设置为强连通分量在链上最右能够到达的点。
如果把第\(i-1\)个节点并入第\(i\)个节点的\(S1\),考虑\(S1\)向\(i-1\)的所有连边的边集\(E\)(不需要考虑\(S1\)内部的连边,因为以前已经合并过了,也不用考虑 从\(i-1\)到\(S1\)的边集,因为现在\(i-1\)到\(S1\)就是可达的了,也不需要考虑外面的边集),对于所有\(E\)上的边,假设从环上的第\(x\)个点连到了第\(y\)个点,我们需要把环上的\(x...y\)合并成同一强连通分量。用并查集维护。
考虑我们合并完后,可能当前点和环上第\(r_i+1\)个点也要合并,考虑可以合并的充要条件:考虑能够到达第\(r_i+1\)个点的边集合\(S\),第\(r_i\)个点能够到达\(S\),可以判定\(S\)中的每个节点是否和\(r_i\)处在同一强连通分量中。
考虑合并,我们事实上考虑\(r_i+1\)的\(S1\)向\(i\)的\(S1\)的所有连边的边集\(E\),对于所有\(E\)上的边,假设从环上的第\(x\)个点连到了第\(y\)个点,我们需要把环上的\(x...y\)合并成同一强连通分量。用并查集维护。
找边可以用链表和类似启发式合并的思想维护。