ShinriiTin/contest/cf966

D. Aztec Catacombs

题意

有一个\(n\le3\times10^5\)个点的无向完全图，每条边的状态会在存在与不存在之间变化。

一开始有\(m\le3\times10^5\)条边存在，每当使用任意一条边\((u, v)\)从\(u\)移动到\(v\)之后，与\(u\)相连的所有边的状态都会改变。

问从点\(1\)移动到点\(n\)，最短的路径，若有多解则任意输出一个，若无解输出-1。

题解

如果有解，不会多于5步。

• 第一种情况，之间走原来的边一次性到达。
• 第二种情况，需要\(4\)步：\(1\to a, a\to b,b\to c, c\to 1, 1\to n\)，其中\((1, a), (a, b), (b, c)\)在原图中存在，\((1,c),(1,n)\)在原图中不存在。

如果\((1,n)\)在原图中存在，显然一步即可到达，因此只要找一个点\(c\)到点\(1\)的最短路等于\(2\)即可。

最优解不可能走更长的路来回到点\(1\)，因为这样要么可以走更短的路径到达跳跃点，要么可以使用更早的跳跃点。

同理，如果第一种情况如果走大于\(4\)步，一定可以通过跳回点\(1\)的方式得到一个\(4\)步的解。

• 第三种情况，需要\(5\)步：\(1\to a, a \to b, b \to c, c \to a, a\to n\)，其中\((1, a), (1, b), (1, c), (a, b), (b, c)\)在原图中存在，\((a, c)\)在原图中不存在，并且因为我们需要使用这种方法来得到最优解，一定不存在任何与\(1\)连通的点直接与\(n\)有边相连，而与\(1\)连通的点一定与\(1\)直接相连。因此，如果必须要走大于\(3\)步回到\(a\)，则直接可以一开始就从\(a\)到跳跃点的前一个点，然后从跳跃点回去，答案不可能超过\(5\)步。

这种情况的重点在于找到这样的\(a, b, c\)，而\(a\)与\(c\)完全是对称的。

我们可以首先删去点\(1\)，

然后从任意一个与\(1\)相连的点出发进行bfs，如果找到一个最短路长度等于\(2\)的点，那么我们就找到了答案；

否则，我们考虑这个点是点\(b\)的可能性，枚举其出边，找到两个不直接相连的点，则其分别为\(a\)和\(c\)，这一步可以用两个vis数组来实现；

如果依然不满足，那么当前与枚举的点连通的点不可能是\(a, b, c\)中的任意一个点了，把它们从图中删去就好。

时空复杂度\(O(n)\).