Time-7 - METEORITE

この問題は UnionFind(素集合データ構造)、逆の操作 を問います。

問題文では辺を削除する、といった操作が必要になりますが、この操作の実装は容易ではありません。
なので、次のように逆の操作をする方が良さそうです。

• すべてのイベントが終わった後の状態のグラフを構築し、与えられるグラフの辺の情報を矛盾なく追加していく

「すべてのイベントが終わった後の状態」とは、辺の情報に頂点番号 $x_1,x_2,...,x_Q$ が含まれていた時、その辺は採用されていないグラフを言います。
その後、イベントでは $j=1,2,...,Q$ として行っていましたが、逆の操作のため $j'=Q,Q-1,Q-2,...,1$ の順で、次の操作を行います。

• 頂点 $x_{j'}$ をグラフに追加する、すなわち $x_{j'}$ を含む辺を追加していく

こうして操作後にできるグラフは入力に与えられたグラフと等しくなります。よってこの逆の操作が適切であることがわかります。

また $Q-j'(=j)$ 回目の操作毎に、毎回頂点 $1$ から頂点 $N$ へのパスの存在判定を、DFSなどの探索法を用いると最悪 $O(Q(N+M))$ だけかかり、時間制限に間に合いません。なのでこの判定を高速に行う必要があります。

そこで、伝家の宝刀であるUnionFind(素集合データ構造)を用いることで、この判定を $O(\alpha(N))$ ※で実装することができます。

最終的に答えるべき値は、この操作をはじめ、初めて頂点 $1$ から頂点 $N$ をつなぐパスが存在するときの $j'$ を $J$ とおくと、$Q-J$ となります。なおこの判定がすべての $j'$ に対し、頂点 $1$ から頂点 $N$ をつなぐパスが存在するなら、答えは Reachable となります。

以上からこの問題は $O(M+Q\alpha(N))$ で実装することができました。以下が解答例になります。

• C++

• Python