메모리: 65320 KB, 시간: 692 ms
그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
첫째 줄에 연결 요소의 개수를 출력한다.
DFS를 사용해 함수를 돌게 했다.
for문을 돌면서 방문하지 않은 노드가 있다면 dfs 함수를 돌도록 하고, cnt 값을 증가시킨다.
dfs를 돌면서 방문한 노드는 방문처리 해준다.
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(start):
visited[start] = True
for i in graph[start]:
if not visited[i]:
visited[i] = True
dfs(i)
return True
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
cnt = 0
for i in range(1, n + 1):
if not visited[i]:
dfs(i)
cnt += 1
print(cnt)