素直に問題文を言いかえせずに解いたら解けるという変わったパターンだった。 制約が最大５０＊５０なことを重視するべきだった。 辺を一つ減らして毎回 Union-find をして一つの木でなかったら (大きさが N でなかったら）ans += 1 するという方針 n, m = m…

Union-find の練習 何回でもスワップできるので、結局 i と p[i]-1 が同じ木にいるかどうかで求まる。 import sys input = sys.stdin.readline n,m = [int(i) for i in input().split()] p = [int(i) for i in input().split()] p = tuple(p) chk = [[set(),…

Union-find木 の練習 Union-find のライブラリーはじゅっぴーさんのをそのまま使わせていただいております。 蟻本 python Union-Find木 競技プログラミング - じゅっぴーダイアリーUnion-find はつなげることしかできないので、入力を逆向き (append でなく …