[코드트리] 그래프 탐색 Python

# n, m 입력
n, m = map(int, input().split())
# graph
graph = [
    [0] * (n+1)
    for _ in range(n+1)
]
# x, y 입력
for _ in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

# dfs(vertex)
def dfs(vertex):
    # 전역 변수 선언
    global ans

    for curr_v in range(1, n+1):
        # 이어져 있고, 방문한 적 없으면
        if graph[vertex][curr_v] and not visited[curr_v]:
            # 정답 올려주고
            ans += 1
            # 방문 처리후
            visited[curr_v] = True
            # 재귀호출
            dfs(curr_v)

# 설계
# ans
ans = 0
# visited
visited = [ False for _ in range(n+1) ]
# root_vertex
root_vertex = 1
# 방문 표시
visited[root_vertex] = True
# dfs
dfs(root_vertex)

# 출력
print(ans)