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

애이용·2021년 1월 20일
0

BOJ

목록 보기
21/58
post-thumbnail

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 이다

profile
로그를 남기자 〰️

0개의 댓글