Union Find

AOJ 2893: Balanced Edge Deletion

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…

ARC 039 D - 旅行会社高橋君

問題 https://beta.atcoder.jp/contests/arc039/tasks/arc039_d 解法 橋を2回通らずに A->B->C の移動が出来るかという問題になる。まず橋を検出し、それらを取り除くと、グラフはいくつかの連結成分に分かれる。各連結成分内では頂点間を移動する経路が常に…