2019-10-30から1日間の記事一覧

DAGの橋?

なんか初めて見たので。 DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定) DAGを無向グラフとみなして橋を求めるのはダメです。 4頂点4辺で、辺がそれぞれ 1 2 2 3 1 4 2 4 を結ぶような…

サイクル基底・サイクルの個数について

チームでICPC練をしていたらサイクルの数を数える問題に遭遇した(Count Cycles: Asia Tsukuba Regional 2017) サイクル基底を知らずに解けたけど(追記: 解けてなかった)サイクル基底を知らなかったのでついでに調べた。 サイクル基底 まず直感的な説明をしま…