DAGの橋?

なんか初めて見たので。

DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定)

DAGを無向グラフとみなして橋を求めるのはダメです。

4頂点4辺で、辺がそれぞれ

1 2
2 3
1 4
2 4

を結ぶようなケースで辺(1,2)を除くと1から3に到達できなくなります。

これは、tから逆辺で到達できる頂点のみに注目してグラフを作り直し、無向グラフだとみなして橋を求めればいいです。