10775 공항

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

큰 번호의 게이트부터 도킹해야 최대한 많은 비행기를 도킹할 수 있다. 파인드 연산을 통해 이미 도킹했다면 앞의 게이트와 연결 시켜서 다음 도킹할 자리를 빨리 찾을 수 있다. 파인드 연산 결과가 0이라면 더 이상 도킹할 자리가 없으므로 종료 시켜주면 된다.

#include <cstdio>
 
int n,m,t,c,r,p[100001];
int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        scanf("%d",&t);
        r=Find(t);
        if(r!=0) p[r]=r-1,c++;
        else break;
    }
    printf("%d",c);
    return 0;
}