[ 20955 ] [ Union-Find ] 민서의 응급 수술

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

20955번: 민서의 응급 수술

 

풀이 과정

---

1. 입력된 뉴런 a와 b가 같은 집합 내에 속해있는지 검사한다.
   1. 같은 집합 내에 속해있지 않다면 Union
   2. 같은 집합 내에 속해있다면 해당 뉴런은 끊어내야 하는 뉴런이므로 연산 횟수를 하나 증가시킨다.
2. 모든 뉴런들에 대해 같은 집합에 속해있는지 검사한다.
   1. 다른 집합에 속해있다면, 두 집합을 Union 해주고 연산 횟수를 하나 증가시킨다.
3. 연산 횟수를 출력시켜준다.

---

소스 코드

---

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())

parent = [i for i in range(N+1)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
        
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

answer = 0

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
    else:
        answer += 1

parent_node = find(parent, 1)
idx = 1
for i in range(2, N+1):
    if find(parent, i) != parent_node:
        union(parent, i, idx)
        parent_node = find(parent, i)
        idx = i
        answer += 1

print(answer)