[백준 파이썬] 11724번 연결 요소의 개수

백준 11724번 연결 요소의 개수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

파이썬 풀이

import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int,input().split())
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [] # 방문 노드 저장

# 그래프 생성
for _ in range(M):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# dfs
def dfs(a):
    if a in visited:
        return

    visited.append(a)

    for node in graph[a]:
        dfs(node)

cnt = 0 # 연결 요소 개수

for i in range(1, N+1):
    if i not in visited: # 탐색하지 않은 정점 dfs 탐색
        dfs(i)
        cnt += 1 # dfs 탐색이 마치면 연결 요소 +1

print(cnt)