考え方 回答例 考え方入力例として， 3 3 1 2 2 3 3 1を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．すでに頂点をつないだかどうかはsetで管理すれば良い．回答例スタックを使えばDFSになり，キューを使えばBFSになる．…

考え方 回答例 考え方全点対最短経路問題（すべての2頂点間の最短路を求める問題）が解けていれば， ある2頂点を結ぶ辺は， その2頂点を迂回する（複数の辺を使う）ことで，同じコスト「以下」で到達できるならなくてもよい（※1） ことからこの問題も解ける…