백준, 연결 요소 개수, 11724, 파이썬

[유형]

DFS

 

[문제링크]

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

 

[요약]

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

[문제풀이]

백준 온라인 저지의 기본 recursionlimit은 1000이다.
sys.setrecursionlimit()을 지정해주지 않으면 재귀 호출 시 런타임 에러가 발생한다.

visited[i]==0인 노드가 없어질 때까지 DFS를 수행하면서 answer+=1

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline().rstrip()

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


n,m = map(int,input().split())
answer = 0
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)

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

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