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

백준 11724번 파이썬 풀이

<문제>

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

11724번: 연결 요소의 개수

 

<풀이>-DFS알고리즘 사용!!!

전형적인 DFS알고리즘 문제이다. 풀이는 밑에 링크에서 확인 할 수 있다.

https://hae-sooo97.tistory.com/25?category=925334

탐색(DFS/BFS)

※주의할점※

파이썬은 재귀호출제한이 걸려있기 때문에 다음과 같은 코드를 반드시 작성해야 런타임에러를 방지할 수 있다.

import sys
sys.setrecursionlimit(10000)

 

 

<코드>-파이썬

import sys
sys.setrecursionlimit(10000)

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


n,m = map(int,sys.stdin.readline().split())

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

visited = [False]*(n+1)

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

count = 0

for i in range(1,len(graph)):
    if not visited[i]:
        count+=1
        dfs(i)
        
        

print(count)