perogram

union find

最小全域木 MST (minimum spanning tree)

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3589709#1 解法 Kruskal法を使う 同じグループ判定にUnion Findを使う エッジコストの小さい順に取り出…

No.74 貯金箱の退屈

Quiz https://yukicoder.me/problems/no/74 Submit https://yukicoder.me/submissions/339953 解法 1枚だけでflipできるコインを調べておく 2枚flipのとき a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく 「一緒にflipできるグループ」ごとに…

No.416 旅行会社

Quiz https://yukicoder.me/problems/no/416 Submit https://yukicoder.me/submissions/339563 解法 破壊される辺以外を張っておく 破壊クエリを逆から読みながらその辺を復活させていく 木がつながったかはUnion Findで管理する 辺を繋げる前に、今回の接続…

F - Asya And Kittens

Quiz https://codeforces.com/contest/1131/problem/F Submit https://codeforces.com/contest/1131/submission/50398023 Note 問題文の図の通り、union find木などで結合していく グループ毎にメンバー一覧を持っておく 結合した時、グループAとグループBの…