AtCoder Regular Contest 037 B – バウムテストをPython3で解く

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

出典：
AtCoder Regular Contest 037 B – バウムテスト

グラフが木……ってそっちかーい。問題自体は難しくないが、木の定義・基礎的な性質を知っておく必要はある。

# AtCoder Regular Contest 037 B - バウムテスト
# https://atcoder.jp/contests/arc037/tasks/arc037_b
# tag: グラフ 木 閉路 BFS DFS 高橋君 典型問題

# 閉路検出の典型問題。
# BFS、もしくは DFS で各連結成分の探索を行い、
# 途中で訪問済みの頂点が現れた場合は
# 閉路が存在する ＝ 木では無い。
# 逆に閉路が存在しなければ、木となる。

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 u, v in path_dat:
        paths[u-1].append(v-1)
        paths[v-1].append(u-1)

    result = 0

    visited = [False] * N

    # 各頂点をスタートとして、連結成分を全てチェックしていく
    for start in range(N):
        # 訪問済みならスキップ
        if visited[start]:
            continue

        # 木かどうかのチェック用
        is_tree = True

        visited[start] = True
        queue = [(-1, start)]
        while queue:
            prev, now = queue.pop()
            for nxt in paths[now]:
                # 一つ前に戻る経路はスキップする。
                if nxt == prev:
                    continue
                # 訪問済みの頂点が現れたら、木では無い。
                if visited[nxt]:
                    is_tree = False
                    continue
                visited[nxt] = True
                queue.append((now, nxt))

        # 木なら回答に +1
        result += is_tree

    print(result)

main()

arc037_b.py view raw

関連

コメントを残すコメントをキャンセル