공항

• Disjoint Set을 이용해서 인접한 숫자들을 그룹으로 묶어서 관리하는 테크닉을 사용하는 문제이다.
• 동일한 테크닉을 사용하는 거의 비슷한 문제로 호텔 방 배정이 있으니, 테크닉에 대한 설명은 그쪽을 참조.
• 시간복잡도는 n이 비행기의 수, m이 게이트의 수 일때, O(m+n*α(m))이 된다

"""Solution code for "BOJ 10775. 공항".

- Problem link: https://www.acmicpc.net/problem/10775
- Solution link: http://www.teferi.net/ps/problems/boj/10775

Tags: [Disjoint Set]
"""

import sys
from teflib import disjointset


def main():
    G = int(sys.stdin.readline())
    P = int(sys.stdin.readline())
    g = [int(sys.stdin.readline()) for _ in range(P)]

    dsu = disjointset.DisjointSet(G)
    gate_by_set = list(range(G))
    for i, g_i in enumerate(g):
        set_id = dsu.find(g_i - 1)
        gate = gate_by_set[set_id]
        if gate is None:
            answer = i
            break
        if gate == 0:
            gate_by_set[set_id] = None
        else:
            prev_gate = gate_by_set[dsu.find(gate - 1)]
            gate_by_set[dsu.union(gate, gate - 1)] = prev_gate
    else:
        answer = P

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet