yukicoder No.416 旅行会社

問題概要

$N$頂点$M$辺のグラフが与えられる。辺の削除が$Q$回行われる。頂点$2,\dots,N$について頂点$1$と非連結になったタイミングを答えよ。

解法

後ろから考えれば辺の追加を行っていき、頂点$1$と連結になったタイミングを答える問題に帰着できる。これは他の解説通りマージテクにより可能で、時間計算量$\Theta(N \log N)$になる。しかし素集合の要素の列挙と併合を扱うデータ構造を用いることにより頂点$x$と連結な要素の列挙を時間計算量$\Theta(x$と連結な成分数$)$で行うことができ、高速化できる。普通のUnionFindがボトルネックとなり時間計算量$\Theta(N\alpha(N))$となる。 実装も軽い。