けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

二重辺連結成分分解・二重頂点連結成分分解

AtCoder ABC 075 C - Bridge (緑色, 300 点)

Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…

AOJ 2893 均衡な辺削除 (AUPC 2018 day3 E)

あの激熱展開を繰り広げた会津合宿北大セットの E 問題。 「橋以外を壊した方がいいケースもある」ということに終盤間際で気づいてからの、残り 14 秒で通せたのは感動した!!!!!!! こたつがめさん・シンヤカトーありがとーーー コンテストでは、「二…

AtCoder ARC 039 D - 旅行会社高橋君 (橙色)

二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…

Educational Codeforces 046 E - We Need More Bosses (R2100)

二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。できるだけ多くの辺を壊したい。うまく s, t…