[10775] 공항

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

10775번: 공항

사용할 수 있는 게이트중 번호가 큰 것 부터 도킹하는것이 유리하다.

유니온 파인드에서 정점 번호가 작은쪽으로 합쳐주면 남아있는 게이트중 가장 번호가 큰 것을 쉽게 찾을 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

class UF {

   public:

    vector<int> p;

    UF(int n) { p = vector<int>(n + 1, -1); }

    int find(int cur) {

        if (p[cur] < 0) return cur;

        return p[cur] = find(p[cur]);

    }

#define union _union

    void union(int A, int B) {

        A = find(A), B = find(B);

        if (A == B) return;

        if (A < B)

            p[A] += p[B], p[B] = A;

        else

            p[B] += p[A], p[A] = B;

    }

};

int g, p, ans;

bool chk[100010];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> g >> p;

    auto uf = UF(123456);

    while (p--) {

        int x;

        cin >> x;

        int tar = uf.find(x);

        if (tar == 0 or chk[tar]) break;

        chk[tar] = true;

        uf.union(tar, tar - 1);

        ans++;

    }

    cout << ans;

    return 0;

}

---