연결 요소의 개수 풀이

문제 링크: https://www.acmicpc.net/problem/11724

백준 알고리즘 기초 2/2 600에서 3번째 - 11724번 연결 요소의 개수를 풀어보았다.

 

풀이: 재귀허용 범위를 넓혀주고, dfs로 탐색한다. https://yuna0125.tistory.com/66 를 참고했다.

 

C++

 

Python

import sys
sys.setrecursionlimit(100000)

def dfs(v):
	visit[v]=True
	for i in mat[v]:
		if not visit[i]:
			visit[i]=True
			dfs(i)

n,m=map(int,input().split())
mat=[[] for i in range(n+1)]
cnt=0
for i in range(m):
	a,b=map(int,sys.stdin.readline().split())
	mat[a].append(b)
	mat[b].append(a)
visit=[False]*(n+1)
for i in range(1,n+1):
	if not visit[i]:
		dfs(i)
		cnt+=1
print(cnt)

Java