グラフ

ICPC模擬国内2016b:D 夏合宿の朝は早い

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748&lang=jp 問題 各頂点が確率を重みとして持つような頂点からなる有向グラフが与えられる。 また、各頂点は確率で状態Aとなる。状態Aとなった頂点は、隣接する頂点の状態をAに変えることが出来…

強連結成分分解

次のサイトを参考にさせていただきました。 一応自分で使いやすい感じにカスタマイズさせていただきました。 強連結成分分解(Strongly-Connected-Components) | Luzhiled’s memo 解説 トポロジカルソートの要領で各頂点からdfsして、帰りがけに頂点を追加し…

ICPC国内予選2014E: 橋の撤去/Bridge Removal

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196&lang=ja 問題 頂点辺からなるグラフ(つまり木)が与えられる。 最初、好きな島に居るとして繰り返し以下のいずれかの操作が可能。 今いる頂点の隣の頂点に移動する。 今いる頂点に生えている…

E. Directing Edges

Codeforces Round #656 (Div. 3) https://codeforces.com/contest/1385/problem/E 問題 頂点辺のグラフが与えられる。 ここで、与えられる辺は、有向辺または無向辺のどちらかである。 無向辺に向きを付けることで、DAGを構成できるかどうか判定せよ。 判定…

E1. Weights Division (easy version)

Codeforces Round #661 (Div. 3) https://codeforces.com/contest/1399/problem/E1 問題 頂点1を根とする頂点からなる木が与えられる。 また、各辺には重みが付けられている。 操作を1度行うたび、任意の重みをに更新することが出来る。 根から葉へのパスの…

模擬国内2018E: 分割統治

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2885&lang=jp 問題 色A, B, C で与えられたグラフを次の条件を満たすように彩色する問題を考える。 AとBで彩色された頂点は、辺で直接繋がっていない。 同じ色で彩色された頂点は、辺で直接繋がっ…