10775 공항 (Union Find)

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

10775번: 공항

 

유니온 파인드로 이런게 가능할지 몰랐다.

Set을 사용한 풀이가 더 직관적인 것 같긴 하지만 유니온파인드가 조금 더 편한 느낌이 있다.

 

풀이는 다음과 같다.

1. parent 배열 초기화.

2. 값 x를 입력받으면 find(x)와 find(x-1)을 merge.     (2-1. 이 때 find(x)의 부모가 find(x-1)인 구조가 되어야 한다.)

     (2-2. merge 할 때마다 ans++)

3. 만약 find(x)가 0이면 자리가 없다는 의미이므로 break;

4. cout<<ans;

 

#include<bits/stdc++.h>
using namespace std;

int parent[100'003];
int ans;

int find(int cur){
    if(cur==parent[cur]) return cur;
    return parent[cur]=find(parent[cur]);
}

void merge(int u, int v){
    u=find(u); v=find(v);
    if(u==v) return;
    parent[v]=u; //u에 v를 붙인다.
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int p,g; cin>>p>>g;
    for(int i=1;i<=p;i++) parent[i]=i;
    while(g--){
        int x; cin>>x;
        if(find(x)==0) break;
        merge(find(x)-1,find(x));
        ans++;
    }
    cout<<ans;
    return 0;
}