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

연결요소 (Connected Component)란?

• 정점사이에 겹치는 정점이 있는 연결되어 있는 그래프로 왼쪽의 연결요소 개수는 2개, 오른쪽의 연결요소 개수는 3개이다.
• 연결요소가 성립될 수 있는 조건은 두 가지가 있다.
  • 하나의 연결요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
  • 다른 연결요소와 같은 정점을 경유하면 안된다.
• 연결요소는 DFS나 BFS탐색을 통해 구할 수 있다.

문제

11724번: 연결 요소의 개수

입력

• 첫째 줄에 정점의 개수 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

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

출력 예제

2

1

문제 풀이

• 1번 정점부터 모든 정점을 돌면서 방문되지 않은 정점이 있다면 방문한 후 , 방문 처리
• 이후 다음 정점에 대해서 이전 정점을 방문할 때 이미 탐색을 마쳤다면 서로 같은 곳을 경유하는 것이므로 같은 연결요소라고 보고 탐색을 진행하지 않는다.
• 위 과정을 모두 반복하면서 탐색이 새로 진행될 때 마다 그래프가 연결되어있지 않은 것이므로, 연결요소의 개수를 카운트한다.
• 연결요소의 개수를 출력한다.

 

BFS 코드

from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = 1
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = 1
                queue.append(i)

cnt = 0
for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)
        cnt += 1

print(cnt)

DFS 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,m = map(int,input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

cnt = 0
for i in range(1, n + 1):
    if not visited[i]:
        dfs(i)
        cnt += 1
print(cnt)