Dynamic connectivity contest: Disconnected Graph
問題概要
n 頂点 m 辺の無向グラフが与えられる。与えられた c 個の辺を削除したときグラフが連結かどうかを判定するクエリを k 個処理せよ。
- 1≦n≦10000
- 1≦m≦100000
- 1≦k≦100000
- 1≦c≦4
解法
オフライン問題なので、以下の問題と同様に解ける。
A が解ければ簡単。
n 頂点 m 辺の無向グラフが与えられる。与えられた c 個の辺を削除したときグラフが連結かどうかを判定するクエリを k 個処理せよ。
オフライン問題なので、以下の問題と同様に解ける。