[11724]연결 요소의 개수 구하기

방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구하는 프로그램 작성

sys.setrecursionlimit(10000)

https://fuzzysound.github.io/sys-setrecursionlimit
만약 재귀를 사용해서 풀어야 하는 문제라면, 위 코드를 상단에 쓰는 것은 필수. 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편.

[[] for _ in range(n)]

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=wjddudwo209&logNo=221253421426

• 2차원 배열을 선언할 때 []*n 사용하지 말고 for로 선언해주어야 각각의 배열을 선언할 수 있다.
• 1차원 배열은 []*n으로 해도 상관 없는 듯 하다

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

# n:노드 개수, m:에지 개수
# A: 그래프 데이터 저장 인접 리스트
# visited 방문 기록 리스트
n, m = map(int, input().split())
A = [[] for _ in range(n+1)]
visited = [False] * (n+1)

# DFS 구현
# visited 리스트에 현재 노드 방문 기록
# 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행(재귀 함수 형태)
def DFS(v):
    visited[v] = True
    for i in A[v]:
        if not visited[i]:
            DFS(i)

# for m의 개수만큼 반복:
# A 인접 리스트에 그래프 데이터 저장
for _ in range(m):
    s, e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)

count = 0

# for n의 개수만큼 반복
# if 방문하지 않은 노드가 있으면:
# 연결 요소 개수 값 1 증가
# DFS 실행
for i in range(1, n+1):
    if not visited[i]:
        count += 1
        DFS(i)
# 연결 요소 개수 값 출력
print(count)
print(A)
print(visited)