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

pekempeyのブログ

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

Dynamic connectivity contest: Disconnected Graph

問題ページ 問題概要 n 頂点 m 辺の無向グラフが与えられる。与えられた c 個の辺を削除したときグラフが連結かどうかを判定するクエリを k 個処理せよ。 1≦n≦10000 1≦m≦100000 1≦k≦100000 1≦c≦4

Dynamic connectivity contest: Connect and Disconnect

こんなコンテストがあったんですね。 問題ページ 問題概要 辺の追加 辺の削除 連結成分の個数を求める という 3 種類のクエリが与えられるので順次処理せよ。

東京大学プログラミングコンテスト2012: 森ですか? dynamic connectivity

http://utpc2012.contest.atcoder.jp/tasks/utpc2012_03 想定解はこの記事の解法より簡単です。 次の PDF を参考にしました。 https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides08.pdf この PDF すごく分かり…