[백준]2606번

1. 문제

2. 소스코드

n = int(input())
m = int(input())

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)
    
cnt = 0
visited = [0]*(n+1)

def dfs(start):
    global cnt
    visited[start] = 1
    for i in graph[start]:
        if visited[i] == 0:
            dfs(i)
            cnt += 1
dfs(1)
print(cnt)

3. 해설

for _ in range(m):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)
    
#[ [],
#  [2,5],
#  [1,3,5],
#  [2],
#  [7],
#  [1,2,6],
#  [5],
#  [4]
#]

=> 이런식으로 그래프가 만들어진다.

def dfs(start):
    global cnt
    visited[start] = 1
    for i in graph[start]:
        if visited[i] == 0:
            dfs(i)
            cnt += 1
           
# dfs(1) 
# visited[1] = 1
# i in graph[1] (graph[1] = [2,5])
# visited[2] == 0 이므로 dfs(2) 실행

# dfs(2)
# visited[2] = 1
# i in graph[2] (graph[2] = [1,3,5])
# visited[1] != 0
# visited[3] == 0 이므로 dfs(3) 실행

# dfs(3)
# visited[3] = 1
# i in graph[3] (graph[3] = [2])
# visited[2] != 0 그리고 cnt+=1

=> 방문하지 않은 노드면 dfs재귀 호출