백준 - 10775 공항

문제 링크입니다 : https://www.acmicpc.net/problem/10775

10775번: 공항

 

유니온 파인드 문제였다. 

 

 

 

 

 

 

#include <iostream>

using namespace std;

int G, P;

int parent[100001];
int gate[100001];

int findParent(int a) {
    if(parent[a] == a) return a;
 
    return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    parent[a] = b;
}

int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);


    int cnt = 0;


    cin >> G >> P;
    for(int i = 1; i <= G; i++) {
        parent[i] = i;
    }

    for(int i = 1; i <= P; i++) {
        cin >> gate[i];
    }

    int temp;
    for(int i = 1; i <= P; i++) {
        temp = findParent(gate[i]);
        if(temp == 0) break;

        unionParent(temp, temp - 1);
        cnt++;
    }

    cout << cnt;

    return 0;
}

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~