[백준 알고리즘/Python] 11724 연결 요소의 개수

문제

 

문제 이해

dfs를 돌면서 쭉 깊이 들어가면 그 한번의 사이클이 연결 요소 입니다.

python의 제귀 제한이 걸려 있어서 sys.setrecursionlimit(10000) 해야 런타임 에러를 해결할 수 있습니다.

그리고 input()으로 입력을 받으면 시간초과가 나기 때문에 sys.stdin.readline을 써서 입력을 받아줍시다.

 

코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

#DFS 메서드 정의
def dfs(v):
    #현재 노드를 방문 처리
    visited[v] = True
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

N, M  = map(int,input().split())

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[] for _ in range(N+1)] 

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False for _ in range(N+1)]

#dfs가 끝날 때 카운트
count = 0

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

#정의된 DFS 함수 호출
for j in range(1,N+1):
    if not visited[j]:
        dfs(j)
        count += 1

print(count)