[백준/Python] 20955번 민서의 응급수술

문제 

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

 

소스코드

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

def union(a, b):
    A = find(a)
    B = find(b)
    if A != B:
        if A < B:
            parent[B] = A
        else:
            parent[A] = B

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

def is_connected(a, b):
    return find(a) == find(b)
answer = 0
for i in range(m):
    a, b = map(int, input().split())
    if is_connected(a, b):
        # print("is_con")
        answer += 1
        continue
    else:
        union(a, b)
for i in range(n):
    find(i + 1)
setg = set(parent)
# print(parent)
# print(setg)
answer += len(setg) - 2
print(answer)

 

유니온파인드를 이용한 풀이입니다. 

 

입력을 받을때 두 노드의 집합이 같다면 연결시 사이클이 생기니 answer + 1을 올리고 입력을 무시합니다. (연결을 끊는 효과)

 

야매 유니온 파인드라 랭크 기반 합치기를 구현하면 시간 복잡도가 줄어듭니다. 

 

입력을 받은 후 가지고 있는 원소의 종류를 빼면(연결을 하는 효과) 답입니다.