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

풀이.

그래프의 연결 요소끼리 각 그래프의 위치에 추가하고 깊이 우선 탐색을 실시한다.

visited배열을 이용하여서 현재 위치를 방문했는지 체크를 해주고 방문하지 않은 위치라면 dfs를 실시하고 +1을 한다.

 

소스코드.

 

	import sys
	def dfs(start):
	visited[start] = True
	for i in graph[start]:
	if visited[i] == False and i != 0:
	dfs(i)
	sys.setrecursionlimit(10 ** 6)
	input = sys.stdin.readline
	n, m = map(int, input().split())
	graph = [[0] for i in range(n+1)]
	visited = [False] * (n + 1)
	for i in range(m):
	u, v = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
	answer = 0
	for i in range(1, n+1):
	if visited[i] == False:
	dfs(i)
	answer += 1
	print(answer)

view raw 11724 - 연결 요소의 개수.py hosted with ❤ by GitHub