코드트리 학습하기 - 알고리즘 입문 : DFS/BFS
N, M = map(int, input().split()) # N, M 입력받기
nodes = [list(map(int, input().split())) for _ in range(M)] # 연결된 두 정점 입력받기
# 각 노드의 시작점, 끝점 구분해서 따로 담아두기
start_points = []
end_points = []
for i in range(len(nodes)):
start_points.append(nodes[i][0])
end_points.append(nodes[i][1])
# 2차원 배열 만들기
matrix = [[0 for _ in range(N)] for _ in range(N)]
for start, end in zip(start_points, end_points):
matrix[start-1][end-1] = 1
matrix[end-1][start-1] = 1
# print(matrix)
# 방문한 노드 체크
visited = [False for _ in range(N)]
# dfs 재귀
def dfs(node):
for curr_node in range(N):
if(matrix[node][curr_node] and not visited[curr_node]):
visited[curr_node] = True
# print(visited)
# print((node+1, curr_node+1))
dfs(curr_node)
# 1이 루트노드로 시작
root_node = 0
visited[root_node] = True
dfs(root_node)
count = 0
for i in range(1, len(visited)):
if(visited[i]):
count += 1
print(count)
# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))
#index를 1번 부터 사용하기 위해 n+1만큼 할당합니다.
graph = [
[0 for _ in range(n + 1)]
for _ in range(n + 1)
]
visited = [False for _ in range(n + 1)]
vertex_cnt = 0
def dfs(vertex):
global vertex_cnt
# 해당 정점에서 이어져있는 모든 정점을 탐색해줍니다.
for curr_v in range(1, n + 1):
# 아직 간선이 존재하고 방문한 적이 없는 정점에 대해서만 탐색을 진행합니다.
if graph[vertex][curr_v] and not visited[curr_v]:
visited[curr_v] = True
vertex_cnt += 1
dfs(curr_v)
for i in range(m):
v1, v2 = tuple(map(int, input().split()))
# 각 정점이 서로 이동이 가능한 양방향 그래프이기 때문에
# 각 정점에 대한 간선을 각각 저장해줍니다.
graph[v1][v2] = 1
graph[v2][v1] = 1
visited[1] = True
dfs(1)
print(vertex_cnt)