[백준][Python] 10775: 공항

array의 P들은 같은 gi에 동시에 존재 할 수 없고 교집합도 있을 수 없다.

되도록이면 gi에 도킹하는 것이 효율적이고 불가능하면 gi-1에 도킹하는 식으로 설계한다.

도킹을 완료하면 이전 트리와 union을 통해 통합된 tree로 도킹 가능한 G를 parent node로 관리한다.

import sys
input = sys.stdin.readline

G = int(input())
P = int(input())
parent = [i for i in range(G+1)] 

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

def union(a, b):
    a = find(a)
    b = find(b)
    parent[b] = a

arr = [int(input()) for _ in range(P)]

ans = 0

for v in arr:
    p = find(v)
    if p == 0:
        break
    ans += 1
    union(p-1, p) 

print(ans)

 

gi들을 매칭시키며 tree를 확장시키는데 최종적으로 find호출시 0이 나오게 된다면 이미 기존 트리에 속해있다는 것이다.

즉 상호배타가 깨짐에 따라 공항이 폐쇄된다.