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

11724번: 연결 요소의 개수

실버 2!🥈

정점의 개수와 간선의 개수를 입력하고 간선의 양 끝점을 반복문으로 입력한다. 

그리고 연결 요소(connected component)가 이해가 되지 않아서 그래프를 손으로 그려보고 나서 이해할 수 있었다. 

 

<첫번째 예제>

#정점, 간선 개수
6 5

#간선을 이루는 쌍
1 2
2 5
5 1
3 4
4 6

-----
#출력
2

서로 연결되어 있는 요소가 2개이므로 출력이 2인 것. 

 

즉, 탐색 후 한 요소를 탐색할 때마다 카운트해주면 된다. 

그리고 python은 재귀 제한이 걸려 있어서 제한을 넘으면 런타임 에러를 일으킬 수 있다. 나도 답도 잘 나오는데 런타임 에러가 떠서 찾아보니 아래 코드처럼 sys.setrecursionlimit(10**7)을 입력해줘서 허용 범위를 넓혀줘야 한다고 한다. 

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

 

<완성 코드>

나는 인접 행렬이 아닌 인접 리스트로 구성한다음 문제를 풀었다. 

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

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

matrix=[[] for _ in range(N+1)]
visited=[0]*(N+1)

#인접리스트 채우기
for i in range(M):
    a,b=map(int,input().split())
    matrix[a].append(b)
    matrix[b].append(a)
    
#dfs 함수
def dfs(v):
    visited[v]=1
    for i in matrix[v]:
        if visited[i]==0:
            dfs(i)

#요소 확인
for i in range(1,N+1):
    if visited[i]==0:
        dfs(i)
        count+=1

print(count)