📚 11724 - 연결 요소의 개수

연결 요소의 개수

풀이

연결 요소 : 나누어지 각각의 그래프를 연결 요소라고 한다.

• dfs와 bfs 두 개중 어떠한 것을 사용하든 풀리는 문제이다.
  • 그럴 경우 bfs를 사용하자! (너비 우선 탐색이 시간이 덜 걸린다.)
• 이와 같이 정점의 최대치가 나온 경우는 2차원 배열에서 각 행마다 열의 값을 입력받자
  • 이유로는, append() 메소드를 사용하여 직접 데이터를 입력받으면 시간이 더 걸린다.

소스

from collections import deque
from sys import stdin as s


def bfs(start, graph, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        cur_data = queue.popleft()

        for i in range(1, n + 1):
            if graph[cur_data][i] == 1 and not visited[i]:
                visited[i] = True
                queue.append(i)


n, m = map(int, s.readline().split())

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

visited = [False] * (n + 1)

result = 0

for _ in range(m):
    u, v = map(int, s.readline().split())
    graph[u][v] = 1
    graph[v][u] = 1

for i in range(1, n + 1):
    if not visited[i]:
        bfs(i, graph, visited)
        result += 1

print(result)

채점 결과