10775번: 공항

https://www.acmicpc.net/problem/10775


$O(g+p)$

가능한 뒷 게이트에 비행기를 도킹한다.

#include<cstdio>
int g, p, par[100001], i, x;
int f(int x) { return x^par[x] ? par[x] = f(par[x]) : x; }
int main() {
    scanf("%d%d", &g, &p);
    for (i = 1; i <= g; i++) par[i] = i;
    for (i = 0; i < p; i++) {
        scanf("%d", &x);
        int r = f(x);
        if (!r) break;
        par[r] = r - 1;
    }
    printf("%d", i);
    return 0;
}