백준 20955 [민서의 응급 수술] 파이썬

https://www.acmicpc.net/problem/20955

 

# 백준 20955 민서의 응급 수술
import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())  # N: 노드 수, M: 간선 수

# 그래프 인접 리스트와 방문 배열 초기화
graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]

# 무방향 그래프 입력 받기
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)

add_cnt = 0  # 연결 요소 개수 (추가 간선 수 계산용)
del_cnt = 0  # 삭제해야 하는 간선 수 (사이클 제거용)

# BFS를 통해 연결 요소와 사이클 탐지
for i in range(1, N+1):
    if not visited[i]:
        add_cnt += 1  # 새로운 연결 요소 시작
        visited[i] = True
        q = deque()
        q.append((i, -1))  # (현재 노드, 이전 노드)

        while q:
            curr_node, prev_node = q.popleft()
            for next_node in graph[curr_node]:
                if next_node != prev_node:
                    if not visited[next_node]:
                        visited[next_node] = True
                        q.append((next_node, curr_node))
                    else:
                        # 이미 방문한 노드인데, 현재 탐색 중 노드의 부모가 아니라면 사이클
                        del_cnt += 1

# 사이클 수는 중복 카운팅되므로 2로 나눔 (무방향 간선이므로)
# 연결 요소가 여러 개면, 이를 하나로 연결하려면 (add_cnt - 1)개의 간선이 필요
print(add_cnt - 1 + del_cnt // 2)

간선의 연결을 이용하여 해결하였다.

 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)  # 재귀 깊이 제한 증가 (Find 함수에서 사용 가능하도록 설정)

# Find: 특정 원소의 루트(대표)를 찾는 함수 (경로 압축 적용)
def Find(x):
    if disjoint[x] != x:
        disjoint[x] = Find(disjoint[x])  # 경로 압축
    return disjoint[x]

# Union: 두 집합을 하나로 합침. 사이클이면 False 반환
def Union(a, b):
    a = Find(a)
    b = Find(b)

    if a == b:
        return False  # 이미 같은 집합 -> 사이클 발생

    # 서로 다른 집합이면 하나로 합침
    if a > b:
        disjoint[a] = b
    else:
        disjoint[b] = a
    return True

N, M = map(int, input().split())  # N: 노드 수, M: 간선 수

disjoint = [0] * (N + 1)  # 각 노드의 대표 노드 저장용 배열
total = 0  # 총 연산 횟수 (삭제 + 추가한 간선 수)

# 각 노드는 처음에 자기 자신이 대표 노드
for i in range(1, N + 1):
    disjoint[i] = i

# 간선을 처리하면서 Union 수행
for i in range(M):
    a, b = map(int, input().split())
    if not Union(a, b):  # 사이클이 생겼다면
        total += 1       # 삭제해야 하는 간선 +1

# 연결 요소의 개수를 1로 만들기 위해 필요한 추가 간선 수를 계산
for i in range(1, N + 1):
    if Find(i - 1) != Find(i):  # 현재 노드와 이전 노드가 다른 집합이면
        Union(i - 1, i)         # 둘을 연결하고
        total += 1              # 추가한 간선 수 +1

# 총 삭제한 간선 수 + 추가한 간선 수 출력
print(total)

UNION/FIND를 이용하여 해결한 코드를 첨부한다.