回答
Submission #419154 - AtCoder Regular Contest 032 | AtCoder
街が道で繋がれていて,全ての街をつなぐためには,追加で何本の道を追加しなければいけないかという問題.
言い換えると,繋がれている街同士をグループ化して,グループの数-1を出力する問題.
更に言い換えると,もう10回位名前を聞いているUnion-Findを使う問題.
というわけで,UnionFindを調べて参りました.
最小全域木(クラスカル法とUnionFind) - アルゴリズム講習会
Algorithms with Python / Union-Find
はい,Union-Findさえ実装できれば,あとは数え上げるだけですね.
再帰回数が~~ とか思ってましたけど,実際そんなに再帰しないですよね…w
import sys def find(x): if x == table[x]: return x else: table[x] = find(table[x]) return table[x] def union(x, y): s1 = find(x) s2 = find(y) if s1 != s2: table[s2] = s1 N, M = map(int, input().split()) table = [i for i in range(N)] sys.setrecursionlimit(100001) for i in range(M): a, b = map(lambda x: int(x)-1, input().split()) union(a, b) res = 0 for i in range(N): if table[i] == i: res += 1 print(res - 1)
そして数え上げのところでミスをしていて結構時間食いました…ひええ.