[백준/BOJ] 백준 15586번 : MooTube (Gold)

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

15586번: MooTube (Gold)

질문을 다 저장하고, 질문에서 k의 내림차순으로 정렬하고, 정렬한 순서대로 다시 질문하는 오프라인 쿼리를 이용했다. 해당 질문의 k이상으로 이루어진 간선들만 연결시켜가며 그래프를 만들고 유니온 파인드를 통해 해당 정점의 그룹을 확인하는 과정을 통해 문제를 해결했다.

 

코드

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

int n, q;
vector<tuple<int, int, int>> edge; //(r,정점1,정점2)
vector<tuple<int, int, int>> question; //(k,정점,질문번호)
vector<int> parent(100005);
vector<int> rank_size(100005);
vector<int> group_size(100005);
int make_edge_index; //아직 안만들어진 edge의 시작 인덱스

vector<pair<int, int>> result; //(질문 번호, 답변)

void Pre()
{
	for (int i = 0; i < 100005; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		group_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[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 >> q;

	for (int i = 0; i < n - 1; i++)
	{
		int p, q, r;
		cin >> p >> q >> r;

		edge.push_back(make_tuple(r, p, q));
	}

	for (int i = 0; i < q; i++)
	{
		int k, v;
		cin >> k >> v;

		question.push_back(make_tuple(k, v, i));
	}

	//간선의 가중치를 내림차순으로 정렬
	sort(edge.begin(), edge.end());
	reverse(edge.begin(), edge.end());

	//질문에서 k의 내림차순으로 정렬
	sort(question.begin(), question.end());
	reverse(question.begin(), question.end());

	make_edge_index = 0;

	//질문의 k가 큰것부터 확인하여 트리를 연결한다
	for (int i = 0; i < question.size(); i++)
	{
		int k = get<0>(question[i]);
		int v = get<1>(question[i]);
		int question_number = get<2>(question[i]);

		//가중치가 k이상으로 연결된 가중치만 연결한다
		for (int i = make_edge_index; i < edge.size(); i++)
		{
			//해당 간선의 가중치가 k이상일때
			if (get<0>(edge[i]) >= k)
			{
				Merge(get<1>(edge[i]), get<2>(edge[i]));
			}

			else
			{
				make_edge_index = i;
				break;
			}

			//모든게 연결 되었을때
			if (i == edge.size() - 1)
			{
				make_edge_index = edge.size();
			}
		}

		int this_parent = Find(v);
		int this_result = group_size[this_parent] - 1; //그룹에서 자기 자신 뺴기
		result.push_back(make_pair(question_number, this_result));
	}

	//질문 순서대로 정렬
	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i].second << "\n";
	}

	return 0;
}