연결 요소의 개수
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
그래프 탐색
연결 요소가 무엇인지 알고있나? 를 묻는 문제라고 생각이 들었다. 결국 연결 요소란, 그래프를 이루고 있는 가지의 수 라고 생각하면 편할 것 같다.
1-2-3-4, 5-6
위와같이 그래프가 주어졌을때, 그래프를 이루는 것은
1-2-3-4 와 5-6 두개이고, 이 경우엔 연결 요소가 두개가 되는 것이다.
import sys
sys.setrecursionlimit(10**8)
def dfs(graph,v,visited):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(graph,i,visited)
global count
count = 0
N,M = map(int,input().split())
visited = [False]*(N+1)
graph = [[] for _ in range(N+1)]
for i in range(M):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
for j in range(1,N+1): #1~ 연결되지 않은 노드들도 파악하기 위해 전부 탐색
if not visited[j]:
dfs(graph,j,visited)
count +=1 #연결 요소 = 그래프를 이루고있는 요소들의 숫자
# 그래프 간의 분리된 노드를 의미?
print(count)결국 어디까지 연결되어있는지 모든 노드를 파악해야하기 때문에 DFS를 사용하였고, DFS를 마쳤는데, 방문하지 않은 노드가 남아있다면, 이는 처음에 탐색한 그래프와 연결되지 않은 다른 그래프이기 때문에, 또 탐색하는 과정을 거치며, 연결 요소의 개수를 파악하였다.
Developer