백준 11724 연결 요소의 개수 Python 3

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

11724번: 연결 요소의 개수

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11724.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import defaultdict
sys.setrecursionlimit(500001)
input = sys.stdin.readline

def dfs(v):
    for nv in graph[v]:
        if not visit[nv]:
            visit[nv] = 1
            dfs(nv)

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

cnt = 0
visit = [0]*(N+1)
for v in range(1, N+1):
    if not visit[v]:
        visit[v] = 1
        dfs(v)
        cnt += 1
print(cnt)

---

풀이 과정

풀이 시간 6분

import sys
from collections import defaultdict
#최대 간선이 500000이므로 재귀 제한을 늘린다
sys.setrecursionlimit(500001)
input = sys.stdin.readline

def dfs(v):
	#정점 v의 간선들을 탐색한다
    for nv in graph[v]:
    	#이전에 방문하지 않은 연결된 정점이 있는 경우, 탐색을 이어나간다
        if not visit[nv]:
            visit[nv] = 1
            dfs(nv)

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

#연결 리스트 방식의 무방향 그래프를 구성한다
graph = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

#연결 요소의 개수
cnt = 0
visit = [0]*(N+1)

#정점들을 기준으로 탐색한다
for v in range(1, N+1):
	#이전에 방문하지 않은 정점이라면, 새로운 연결 요소를 탐색한다
    if not visit[v]:
        visit[v] = 1
        dfs(v)
        #연결 요소 수 카운팅
        cnt += 1
        
print(cnt)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)