[백준/BOJ] 백준 13306번 : 트리

www.acmicpc.net/problem/13306

13306번: 트리

유니온 파인드를 이용해서 문제를 해결했다. 그런데 시간 초과를 해결하기 위해, 쿼리에서 전체 에지(n-1개)를 모두 제거하므로 정점이 모두 분리 되있는 경우부터 거꾸로 생각해 나간다. 즉 거꾸로 가면서 에지를 제거하는 쿼리는 에지를 연결하는 식으로 진행한다 그리고 거꾸로 진행했으므로 결과도 뒤집는다.

 

코드

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

int n, q;
vector<int> original_parent(200001);
vector<int> parent(200001);
vector<int> rank_size(200001);
vector<string> result;

struct info {
	int x;
	int b;
	int c;
	int d;
};

vector<info> query;

void Pre()
{
	//모든 정점이 분리된 상황의 트리
	for (int i = 0; i < 200001; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
	}
}

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[v] = u;
	}

	else
	{
		parent[u] = v;

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

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

	Pre();

	cin >> n >> q;

	original_parent[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		int a;
		cin >> a;

		original_parent[i] = a;
	}

	for (int i = 0; i < n - 1 + q; i++)
	{
		int x, b, c, d;

		cin >> x;

		if (x == 0)
		{
			cin >> b;

			query.push_back({ x,b,0,0 });
		}

		else if (x == 1)
		{
			cin >> c >> d;

			query.push_back({ x,0,c,d });
		}
	}

	//쿼리 에서 전체 에지(n-1개)를 모두 제거 하므로
	//정점이 모두 분리 되있는 경우부터 거꾸로 생각해 나간다
	//즉 거꾸로 가면서 에지를 제거하는 쿼리는 에지를 연결하는 식으로 진행한다
	//->시간 초과 문제를 해결하는 방법!

	//쿼리를 뒤집는다
	reverse(query.begin(), query.end());

	for (int i = 0; i < query.size(); i++)
	{
		int x = query[i].x;

		//에지를 연결한다
		if (x == 0)
		{
			int b = query[i].b;

			Merge(b, original_parent[b]);
		}

		else if (x == 1)
		{
			int c = query[i].c;
			int d = query[i].d;

			if (Find(c) == Find(d))
				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;
}