백준 #10775 공항


BOJ #10775 - 공항

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

# 문제 분류

Disjoint-Set

풀이 접근 방법


유니온파인드를 새로운 관점으로 보게 해 준 문제. 방 청소@9938이랑 비슷하다고는 하는데 그건 너무 어려워서 건들지도 못했어서..

이렇게도 유니온파인드를 적용시킬 수 있다~ 정도? 구현은 어렵지 않았다.


#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, G, P, g;

int p[100100];

int find(int n) {
    if (n == p[n])
        return n;
    return p[n] = find(p[n]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    p[b] = a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> G >> P;

    fup(i, 1, G, 1) {
        p[i] = i;
    }

    int cnt = 0;
    fup(i, 1, P, 1) {
        cin >> g;

        int res = find(g);

        if (res) {
            merge(find(g) - 1, find(g));
            cnt++;
        } else {
            break;
        }
    }

    cout << cnt;
}