백준 2606번

 

기본 dfs 문제와 똑같지만 모든 경로를 출력하는게 아니고 count로 경로를 방문할때마다 +1씩 해서 마지막에 count만 출력하는 문제이다.

n = int(input()) # 노드의 개수 (컴퓨터의 개수)
m = int(input()) # 간선의 개수 (연결된 컴퓨터 쌍의 개수)

graph = [[] * n for _ in range(n + 1)]
visited = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0
visited = [False] * (n + 1) # 각 노드가 방문된 정보 저장할 리스트


def dfs(v):
    global count # 전역변수 cnt를 사용하기 위해 global을 붙여줌
    visited[v] = True
    for i in graph[v]:
        if visited[i] == False:
            dfs(i)
            count += 1

dfs(1)
print(count)