2021.3.1 [백준] 공항

서로소 집합 알고리즘(분리 집합 알고리즘)

 

 

Q

 

www.acmicpc.net/problem/10775 

10775번: 공항

 

A

이중 반복문을 이용하여도 풀 수 있으나 시간초과가 된다. 따라서 분리집합 알고리즘을 이용하여야 한다.

 

 

코드

 

def find_parent(x): #루트노드 찾기
    if p[x] != x:
        p[x] = find_parent(p[x])
    return p[x]

def union(x, y): #합집합
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        p[y] = x
    else:
        p[x] = y
        
import sys

gate = int(sys.stdin.readline().rstrip())

fly = int(sys.stdin.readline().rstrip())

array = list(int(sys.stdin.readline().rstrip()) for _ in range(fly))

 

p = [0] * (gate + 1)
for i in range(1, gate + 1):
    p[i] = i

result = 0

for i in range(fly):
    if find_parent(array[i]) == 0: #더이상 들어갈 수 있는 게이트가 없다면
        break
    union(array[i], p[array[i]]-1) #이걸 이용하여 합집합하기
    result += 1

print(result)