[ baekjoon ] 11724. 연결 요소의 개수

11724. 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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. 또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.

DFS 알고리즘을 이용한 코드들이 많았는데,
나는 크루스칼 알고리즘을 이용해, 소스코드를 작성했다

• DFS 알고리즘 추가

UNION

## 11724_연결요소의 개수
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

graph = []
for _ in range(m):
  a, b = map(int, input().split())
  if a > b: # 첫번째 정점 번호를 작게 만듬
    a, b = b, a
  graph.append((a, b)) 

parent = [0] * (n + 1)
for i in range(n + 1):
  parent[i] = i

def find_parent(parent, a): # 특정 원소가 속핮 집합 찾기
  if parent[a] != a:
    parent[a] = find_parent(parent, parent[a])
  return parent[a]

def union_parent(parent, a, b): # 집합 합치기
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  parent[b] = a

graph.sort()

before = 0
# 간선 하나씩 확인
for edge in graph: 
  a, b = edge
  if before == find_parent(parent, a): # 처리됐던 번호(a)와 같으면 pass
    union_parent(parent, before, b)
    pass
  elif before == find_parent(parent, b):
    union_parent(parent, before, a)
    pass
  else: # 부모가 바뀌지 않았으면
    before = find_parent(parent, a)
    union_parent(parent, a, b) # 집합 합치기

print(len(set(parent)) - 1) 
# 첫번째 원소가 0이기 때문에 이것을 제외한 집합 개수 찾기

DFS

import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [False] * (n + 1)
def dfs(v):
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      dfs(i)

result = 0

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

print(result)

python은 재귀제한이 걸려있어서 재귀 허용치가 넘어가면 런타임에러를 일으킨다.
->sys.setrecursionlimit(10000) 작성
기본적으론 1000 이다