[백준/BOJ] 백준 12012번 : Closing the Farm (Gold)

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

12012번: Closing the Farm (Gold)

 

농장을 닫히는 순서대로 닫는 게 아니라, 농장이 닫히는 순서로 거꾸로 하여 모든 농장이 닫힌 상태(끊어진 상태)에서 농장을 하나씩 추가하여 연결하는 오프라인 쿼리를 이용해 문제를 해결했다. 이때 농장의 연결은 유니온 파인드를 이용했다.

 

코드

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

int n, m;
vector<int> adj[200005];
vector<int> close_order;

vector<int> parent(200005);
vector<int> rank_size(200005, 1);
vector<int> group_size(200005, 1);
vector<int> add_check(200005, 0);
int add_cnt = 0; //지금까지 더해진 정점의 개수

vector<string> result;

void Pre() {

	for (int i = 0; i < 200005; 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);

	if (u == v) {
		return;
	}

	if (rank_size[u] < rank_size[v]) {
		parent[u] = v;
		group_size[v] += group_size[u];
	}
	else {
		parent[v] = u;
		group_size[u] += group_size[v];

		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}
}

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

	Pre();

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 0; i < n; i++)
	{
		int close_barn;
		cin >> close_barn;

		close_order.push_back(close_barn);
	}

	//거꾸로 생각하여 모든게 끊어져있고 해당 정점을 추가 하고, 모든 정점이 연결되어 있는지 확인한다

	for (int i = n - 1; i >= 0; i--) {

		//이번에 추가할 정점
		int add_barn = close_order[i];
		add_cnt++;
		add_check[add_barn] = 1;

		for (int j = 0; j < adj[add_barn].size(); j++) {
			int connected_barn = adj[add_barn][j];

			//연결된 정점이 이미 추가 되었을때, 두 정점을 유니온 한다
			if (add_check[connected_barn] == 1) {
				Merge(add_barn, connected_barn);
			}
		}

		//모든 정점이 연결되어 있는지 확인한다
		//add_barn 그룹의 크기랑 지금까지 더해진 총 정점의 수와 같으면 지금까지 모든 정점이 연결되어 있는것이다
		int root = Find(add_barn);
		if (add_cnt == group_size[root]) {
			result.push_back("YES");
		}
		else {
			result.push_back("NO");
		}
	}

	reverse(result.begin(), result.end());

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}