[백준] 11724 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력

2

풀이

부분 배열 이용

입력된 간선 정보를 이용해 2개 이상의 정점이 존재하는 연결 요소를 생성하여 개수를 센다. 이후 간선 정보에 포함되지 않은 정점이 1개만 존재하는 연결 요소의 개수를 세 더해준다.

주의) 그래프에서 다른 것과 연결되지 않은 정점 1개 그 자체도 하나의 연결 요소이다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ans = []
cnt = 0 # 연결요소의 개수
# 언급된 정점들만 부분배열에 들어있음
for _ in range(m): 
    s,e = map(int,input().split())
    sIdx, eIdx = -1, -1
    for idx, lst in enumerate(ans):
        if s in lst: sIdx = idx
        if e in lst: eIdx = idx
    if sIdx != -1 and eIdx != -1: # 둘다 따로 연결요소 있으면 합침 
        if sIdx != eIdx:
            ans[sIdx].extend(ans[eIdx])
            del ans[eIdx]
    elif sIdx != -1: ans[sIdx].append(e) # s만 연결요소 존재
    elif eIdx != -1: ans[eIdx].append(s) # e만 연결요소 존재
    else: ans.append([s,e]) # 둘 다 연결요소 없음
# 언급안된 정점들 개수를 더해줘야 함. 1개 자체도 연결요소 1개이므로
for v in range(1, n+1):
    isExist = False
    for lst in ans:
        if v in lst: isExist = True
    if isExist == False:
        cnt+=1
print(cnt+len(ans))

BFS 탐색 이용

그래프의 정점별 연결 정점 정보를 이용해 각 정점에 대해 for 문으로 bfs 탐색을 실시한다. 만약 bfs 탐색 시 이미 방문한 정점인 경우 바로 탐색을 종료하고, 그렇지 않은 경우 연결 요소 개수를 1 증가시키고 그대로 bfs 탐색을 수행한다.

예를 들어 정점의 개수가 7개인 (1,2,5), (3,4,6), (7) 와 같이 구성된 그래프는 1,3,7 정점을 시작노드로 하여 각각 bfs 탐색을 수행하게 된다.

from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
visitied = [0]*(n+1)
graph = [[] for _ in range(n+1)]
cnt = 0
for _ in range(m):
    f,s = map(int,input().split())
    graph[f].append(s)
    graph[s].append(f)
def bfs(n):
    global cnt
    queue = deque()
    # 방문 안한 요소인 경우 방문 처리
    if visitied[n] == 0: 
        visitied[n] = 1
        queue.append(n)
        cnt+=1 
    # 요소 n과 이어진 모든 요소들 탐색(한개의 연결요소임)
    while queue:
        p = queue.popleft()
        for v in graph[p]:
            if visitied[v] == 0: # 방문안한 방문처리 & 큐 삽입
                visitied[v] = 1
                queue.append(v)
# 그래프 상의 1~n까지의 정점에 대해 bfs 탐색 실시
for v in range(1,n+1): bfs(v)
# 정답 출력
print(cnt)