[백준] 10775번 : 공항

10775번: 공항

해당 문제는 소로소 집합 문제로 G(i)가 4일경우 첫번째 방문을 할때에, 부모를 3으로 가르키게 한다.

3을 가리키게 함으로서 4번 도킹에는 비행기를 이륙 시킨 셈이다. 따라서 이후에 4번이 들어온다고해도 3번을 가르키기 때문에 3번 도킹에 이륙하게된다.

import sys
input = sys.stdin.readline
G = int(input())
P = int(input())
parent = [i for i in range(G+1)]
def find(v1):
    if parent[v1] != v1:
        parent[v1] = find(parent[v1])
        return parent[v1]
    else:
        return parent[v1]

def union(v1, v2):
    p1 = find(v1)
    p2 = find(v2)
    if p1 > p2:
        parent[p1] = p2
    else:
        parent[p2] = p1

cnt = 0
for _ in range(P):
    g = int(input())
    p = find(g)

    if p == 0:
        break

    cnt += 1
    union(p, p-1)

print(cnt)