辺が存在しない場合の辺の削除クエリ

辺が存在しない場合の辺の削除クエリ - ei1333の日記

— 50 (@googol_S0) 2021年7月28日

Dynamic connectivity は、グラフに辺を追加するクエリ、辺を削除するクエリ、2つの頂点が連結か判定するクエリが与えられる問題です。

ところで、辺を削除するクエリがグラフに辺が存在しない場合に与えられると仮定した場合、実は辺の削除クエリが与えられないことを示せます。

したがって、辺を追加するクエリと、連結判定クエリの2つを処理できれば良くて、Union Findを用いることで効率的にクエリを処理することが可能です。