[백준][11724] 연결 요소의 개수

• 문제
  • 11724번: 연결 요소의 개수
• 해결

import sys

sys.setrecursionlimit(99999)

vertex_count, edge_count = [int(x) for x in sys.stdin.readline().strip().split()]

edges = [list(map(int, each.strip().split())) for each in sys.stdin.readlines()]

adj_list = [[] for _ in range(vertex_count + 1)]
chk_list = [False] * (vertex_count + 1)
connected_components = []

for each in edges:
    adj_list[each[0]].append(each[1])
    adj_list[each[1]].append(each[0])

for v in range(1, len(adj_list)):
    adj_list[v] = sorted(list(set(adj_list[v])))

def dfs(vertex, connected_component):
    chk_list[vertex] = True
    connected_component.append(vertex)
    for neighbor in adj_list[vertex]:
        if not chk_list[neighbor]:
            dfs(neighbor, connected_component)

for vertex in range(1, len(adj_list)):
    if not chk_list[vertex]:
        connected_component = []
        dfs(vertex, connected_component)
        connected_components.append(connected_component)

print(len(connected_components))

• 포인트
  • dfs