AtCoder Regular Contest 032 B – 道路工事 をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 032 B – 道路工事

かつてはそれなりに難しかった問題、といった感じだろうか。単純に連結成分数を求める問題である。

# AtCoder Regular Contest 032 B - 道路工事
# https://atcoder.jp/contests/arc032/tasks/arc032_2
# tag: グラフ 連結成分 BFS DFS 大工のチョーさん

# 連結成分数が分かれば、その数 - 1 の道路を
# 作れば、全てを連結にできる。

def main():
    N, M = map(int, input().split())
    path_dat = [list(map(int, input().split())) for _ in range(M)]

    # 隣接リストを作成
    paths = [[] for _ in range(N)]
    for a, b in path_dat:
        a -= 1
        b -= 1
        paths[a].append(b)
        paths[b].append(a)

    # あらかじめ 1引いておく。
    result = -1

    # 連結成分数を数える。
    visited = [False] * N
    for start in range(N):
        if visited[start] == True:
            continue

        result += 1
        queue = [start]

        while queue:
            now = queue.pop()
            for nxt in paths[now]:
                if visited[nxt] == True:
                    continue
                visited[nxt] = True
                queue.append(nxt)

    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。