코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())

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

for i in range(m):
    a, b = map(int, input().split())
    
    graph[a].append(b)
    graph[b].append(a)
    
cnt = 0

visited = [False] * (n+1)

def dfs(graph, v, visited):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

for j in range(1, n+1):
    if not visited[j]:
        dfs(graph, j, visited)
        cnt += 1    
        
print(cnt)        

문제 해설

방향이 없는 그래프일 때, ‘연결 요소’의 개수를 구하는 문제이다.


**연결 요소 **

  • 하나의 그래프가 겹치는 정점없이 각각의 부분으로 나누어져 있을 때, 그 각각의 부분을 의미

    연결 요소

    <출처 : 위키피디아>


DFS를 구현 한 후, 각 노드를 시작점으로 하여 노드마다 DFS를 실행해준다.

  1. 노드와 연결된 노드를 처음 방문하는 경우 방문했다는 것을 체크한다.
  2. 이어서 더 방문할 노드가 없는 경우, 개수를 1 증가시키고 다음 노드로 넘어간다.
  3. 1, 2의 과정을 모든 노드에 대하여 반복한다.

댓글남기기