그래프 - 11724번: 연결 요소의 개수

jisu_log·2025년 8월 16일

알고리즘 문제풀이

목록 보기
84/105


from collections import defaultdict, deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
graph = defaultdict(list)


def bfs(graph, start, visited):
    q = deque()

    q.append(start)
    visited.add(start)

    while q:
        node = q.popleft()

        child = graph[node]

        for c in child:
            if c not in visited:
                q.append(c)
                visited.add(c)

    return visited


all_node = set(range(1, n + 1))  # 1부터 n까지 채우기

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


visited = set()
group_cnt = 0


while len(visited) < n:
    candidates = all_node - visited  # 전체 노드 중 방문하지 않은 노드 집합 구하기
    c = candidates.pop()  # 집합에서 아무거나 하나 뽑아 쓰기

    if c not in visited:
        visited = bfs(graph, c, visited)
        group_cnt += 1


print(group_cnt)

0개의 댓글