【AtCoder】【Python】ABC284 C問題 Count Connected Components

【問題概要】

N頂点 M辺の単純無向グラフの連結成分の個数を求める。

【制約条件】は緩いので割愛

深さ優先探索で連結成分の個数を数えるアルゴリズムは、ばっちり存在→　参考文献

深さ優先探索は、スタックのやり方の方が好きだが、久しぶりなので忘れてしまった。

ので、今回は参考文献の通り、再帰のやり方で行った。

なお、グラフG=(V, E)の深さ優先探索の計算量は、O(V+E)のよう参考文献

N, M = map(int, input().split())
UVlist = [list(map(int, input().split())) for _ in range(M)]

# 深さ優先探索（DFS）
def dfs(graph, seen,i):
    seen[i] = True
    for e in graph[i]:
        if not seen[e]:
            dfs(graph, seen, e)
# 無向グラフを作成
graph = [[] for _ in range(N)]

for uv in UVlist:
    u, v = uv
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

# print(graph)

ans = 0
# 探索リストの初期化
seen = [False for _ in range(N)]

# 深さ優先探索を再帰で行う
for i in range(N):
    if not seen[i]:
        dfs(graph, seen, i)
        # 1つの連結成分を全て探索するとインクリメント
        ans += 1

print(ans)