2019-10-30 DAGの橋? なんか初めて見たので。 DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定) DAGを無向グラフとみなして橋を求めるのはダメです。 4頂点4辺で、辺がそれぞれ 1 2 2 3 1 4 2 4 を結ぶようなケースで辺(1,2)を除くと1から3に到達できなくなります。 これは、tから逆辺で到達できる頂点のみに注目してグラフを作り直し、無向グラフだとみなして橋を求めればいいです。