Atcoder水色精進記録
ABC235
E - MST + 1
https://atcoder.jp/contests/abc235/tasks/abc235_e
アルゴリズム・データ構造
クラスカル法,UnionFind,クエリ並列化
考察
最小全域木になる辺の選び方は、全ての辺をコストが昇順になるようにsortし、
辺の両端が同じrootでなければその辺を利用、既に同じrootであればその辺は利用せずに、次の辺を確認する。利用する辺がN-1まで上記を実施すればOK
計算量はO(MlogM)
各クエリで追加される辺がMSTに含まれるかどうかをMSTが完成している状態から判定するのは難しいので、最初にクエリで追加される辺を全て辺に加えておいて考える。
クエリで追加される辺がMSTに選ばれた場合は、次のクエリに影響を与えないように、MSTには加えずにスキップする処理を追加すれば一度のMSTの構築で全クエリの結果を計算することができる。
提出
感想
クエリを先読みして並列で考える方法が思い浮かんだのは成長を感じる。