11724번. 연결 요소의 개수

https://www.acmicpc.net/problem/11724

 

 

 

참고: 단지 번호 붙이기 https://awesomeroo.tistory.com/35?category=743874

 

 

처음에는 메모리 낭비 방지를 위해 인접 행렬을 인접 딕셔너리로 표현했으나 인접 리스트(이중 리스트)로 바꾸었다.

연결 요소 구하기 문제에서는 동떨어져 있는 무인도 노드도 하나의 연결 요소로 보아야 하기 때문이다.

(인접 딕셔너리에서는 간선이 없는 노드는 key로서 추가되지 않는다)

단지 번호 붙이기 문제와 유사한데, 연결되어 있는 부분 찾기 (Flood fill) 문제 타입이라고 한다.

import sys


def dfs(start):
    stack = [start]
    visited[start] = 1

    while stack:
        node = stack.pop()
        for child in range(1, n+1):
            if graph[node][child]:
                if not visited[child]:
                    visited[child] = 1
                    stack.append(child)



n, m = map(int, sys.stdin.readline().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    graph[u][v] = 1
    graph[v][u] = 1

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

count = 0
for startNode in range(1, n+1):
    if not visited[startNode]:
        dfs(startNode)
        count += 1

print(count)