알고리즘

[알고리즘] 백준 10775 - 공항 (C++)

blueberrysoda 2025. 1. 31. 16:24

[문제 링크] : https://www.acmicpc.net/problem/10775

#include <iostream>
using namespace std;

int G, P;
int Arr[100001];
int Ans;

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

void solve(int a, int b){
    a = find(a);
    b = find(b);

    if(a > b){
        swap(a, b);
    }

    Arr[b] = a;
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> G >> P;
    for(int i=0; i<=G; i++){
        Arr[i] = i;
    }

    int inp;
    for(int i=1; i<=P; i++){
        cin >> inp;
        inp = find(inp);

        if(inp == 0){
            break;
        }

        solve(inp, inp - 1);

        Ans++;
    }

    cout << Ans << "\n";

    return 0;
}