[백준/BOJ] 백준 10775번 : 공항

www.acmicpc.net/problem/10775

10775번: 공항

유니온 파인드를 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int g, p;
vector<int> parent(100001);

void Pre()
{
	for (int i = 0; i < 100001; i++)
	{
		parent[i] = i;
	}
}

//유니온 파인드의 파인드
int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

//유니온 파인드의 유니온
void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	parent[u] = v;
}

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

	int cnt = 0;
	bool finish = false;

	Pre();

	cin >> g;
	cin >> p;

	for (int i = 1; i <= p; i++)
	{
		int gi;

		cin >> gi;

		if (finish) //공항이 폐쇄되었을때
			continue;

		if (Find(gi) != 0) //비행기가 도착할 수 있을때
		{
			cnt++;
			Merge(parent[gi], parent[gi] - 1); //이전 공항과 유니온 한다
		}

		else //비행기가 도착할 수 없을때
			finish = true; //공항 폐쇄
	}

	cout << cnt;

	return 0;
}