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

# 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()