読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Dynamic connectivity contest: Disconnected Graph

Dynamic Connectivity

問題ページ

問題概要

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

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

解法

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

pekempey.hatenablog.com

A が解ければ簡単。