BOJ 10775空港

https://www.acmicpc.net/problem/10775
1秒、256 MBメモリ
input :

第1行はゲートウェイ数G(1≦G≦10^5)

を含む.

第2列は飛行機の数P(1≦P≦10^5)

Pの行にはgi(1≦gi≦G)が与えられる.

output :

が停泊可能な最大飛行機数出力

条件:

i便を1便からgi(1≦gi≦G)ゲートの1つである

に永久に停泊します.

便がいずれの搭乗口にも停泊できない場合、空港は閉鎖され、その後はどの便も到着できません.

優先的に考える方法.
例2.
4
6
2
2
3
3
4
4
2、2、3、3を入力すると、関門に入ることができなくなり、空港は閉鎖されます.
では最大の数字から1まで、このドアに届くかどうかを判断すればいいのです.
2階建てのforゲートを使うと、最悪の場合は10^5*10^5で、飛行機数が10^5の場合、時間が爆発する可能性があります.
こうして見つけたのはunion-findを利用することです.現在ドッキングするゲートウェイが0でない場合は、ドッキングできます.これにより、残りの場所を表示するのではなく、各ゲートウェイを柔軟に接続できます.
最初の飛行機がドッキングする関門の値が0でなければ、飛行機をドッキングすることはできません.
可能であれば、現在の飛行機がドッキングするゲートの親ノードを見つけ、ゲートの親ノード-1に結合します.
2番ゲートでドッキングを行うと、1番ゲートでドッキングを行うことができます.

import sys

def union(a, b):
    # a번 게이트에 도킹을 하면 그 게이트에 다음 비행기가 오면
    # 이것은 a - 1번 게이트에 도킹을 하게 된다.
    # 이를 모든 배열에 적용시키기 위해 union-find를 사용.
    parent_a = find(a)
    parent_b = find(b)

    data[parent_a] = parent_b

def find(x):
    if x == data[x]:
        return x

    data[x] = find(data[x])
    return data[x]

g = int(sys.stdin.readline())
p = int(sys.stdin.readline())
ans = 0

data = [i for i in range(g + 1)]

for i in range(p):
    gate = int(sys.stdin.readline())

    where = find(gate)
    # 현재 gate에 도킹이 가능한가를 판별해야함.
    # 이 gate의 부모가 0에 존재한다면 더 이상 도킹이 불가.
    if where == 0:
        break

    union(where, where - 1)
    ans += 1

print(ans)

ゲートの数を基準にデータを作成する必要がありますが、飛行機の数を基準に作成したため、運転時エラーが発生しました.