読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ARC 032 B - 道路工事(2015/06/04)

回答

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)

そして数え上げのところでミスをしていて結構時間食いました…ひええ.