名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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)

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