バックアップ-グラフ(#11724)

Code 1

import sys

# make adjacent list (graph)
n, m = map(int, input().split())
comp_num = 0
adj_list = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

# dfs & find the number of component
visited = {}
for start_v in range(1,n+1):
    if start_v not in visited:
        stack = [start_v]
        while stack:
            v = stack.pop()
            if v not in visited:
                visited.setdefault(v)
                stack += adj_list[v]
        comp_num += 1

print(comp_num)

Code 2

### using recursion for dfs ###
import sys

sys.setrecursionlimit(10000)
def dfs(v):
    visited.setdefault(v)   
    for i in adj_list[v]:
        if i not in visited :
            dfs(i)

# make adjacent list (graph)
n, m = map(int, input().split())
comp_num = 0
adj_list = {i:[] for i in range(1,n+1)}
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_list[a].append(b)
    adj_list[b].append(a)
            
# dfs & find the number of component
visited = {}
for start_v in range(1,n+1):
    if start_v not in visited:
        dfs(start_v)
        comp_num += 1

print(comp_num)

リファレンス