Dynamic connectivity contest: Disconnected Graph

問題ページ

問題概要

n 頂点 m 辺の無向グラフが与えられる。与えられた c 個の辺を削除したときグラフが連結かどうかを判定するクエリを k 個処理せよ。

  • 1≦n≦10000
  • 1≦m≦100000
  • 1≦k≦100000
  • 1≦c≦4

解法

オフライン問題なので、以下の問題と同様に解ける。

pekempey.hatenablog.com

A が解ければ簡単。