グラフの橋
AtCoder
AtCoder700点
ARC-D
黄色diff
グラフ
二重辺連結成分分解・二重頂点連結成分分解
連結成分
DFS
DFS木やBFS木を考察する
グラフの辺の向き付けに関する問題
強連結成分を考える
解空間:O(2^N)通りの選択肢
グラフの橋
復元
最小回数・最小個数を求める
最小コスト
最適化問題
二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題! 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…
AtCoder
AtCoder300点
緑色diff
ABC-C
グラフ
DFS
BFS
Union-Find
連結成分
非自明な線形時間
二重辺連結成分分解・二重頂点連結成分分解
各kに対して
グラフのconnectivity
クエリ:削除
けんちょん本演習問題
N個のものうち1個を変更・削除したものを解く
【問題集】DFS・BFSのステップアップ
グラフの橋
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…
二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…
グラフ
二重辺連結成分分解・二重頂点連結成分分解
DFS
木
直径
グラフのconnectivity
Codeforces
EducationalCodeforces
CodeforcesR2100
グラフの橋
そのまま覚えたい典型問題
二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。 2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。 できるだけ多くの辺を壊したい。うまく s,…