[백준/BOJ] 백준 1396번 : 크루스칼의 공

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

1396번: 크루스칼의 공

 

문제에 대한 접근은, 간선을 가중치 순으로 정렬하고 각 쿼리에 대해 어떠한 간선까지 합쳤을 때, 쿼리의 출발지에서 목적지까지 가는지 이분 탐색을 통해 구할 수 있다. 출발지에서 목적지까지 갈 수 있는지 여부는, 유니온 파인드에서 출발지와 목적지가 같은 그룹이 되는지 확인하는 방법을 이용했다.

 

하지만 쿼리가 많아, 각 쿼리마다 하나씩 진행하지 않고 병렬 이분 탐색을 이용해서 문제를 해결했다.

 

코드

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

//병렬 이분 탐색을 이용해 문제를 해결

int n, m;
vector<tuple<int, int, int>> edge;
int q;
vector<pair<int, int>> query;

int parent[100005];
int rank_size[100005];
int group_size[100005];
pair<int, int> result[100005];

vector<pair<int, int>> query_range;
vector<int> check_edge_range[1000005]; //[확인할 합쳐지는 간선 범위] = 확인할 합쳐지는 간선 범위까지 간선을 연결했을때 확인하려고 저장해두었던 쿼리들

void pre() {
	for (int i = 0; i < 100005; i++) {
		parent[i] = i;
		rank_size[i] = 1;
		group_size[i] = 1;
		check_edge_range[i].clear();
	}
}

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);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back(make_tuple(c, a, b));
	}

	cin >> q;

	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;

		query.push_back(make_pair(x, y));
	}

	//가중치 순서로 간선 정렬
	sort(edge.begin(), edge.end());

	//쿼리가 탐색해야 확인해야 될 간선 범위를 저장
	for (int i = 0; i < q; i++) {
		query_range.push_back(make_pair(0, m - 1));
	}

	for (int i = 0; i < 100005; i++) {
		result[i] = make_pair(-1, -1);
	}

	while (1) {

		pre();

		bool finish = true;
		for (int i = 0; i < q; i++) {

			if (query_range[i].first > query_range[i].second) { //해당 쿼리의 모든 범위를 확인 했을때
				continue;
			}

			finish = false;
			int mid = (query_range[i].first + query_range[i].second) / 2;
			check_edge_range[mid].push_back(i);
		}

		//병렬 이분 탐색이 끝났을때
		if (finish == true) {
			break;
		}

		//i개의 간선을 연결해보고, i개의 간선을 연결했을때 확인하려고 했던 쿼리들을 확인한다
		for (int i = 0; i < m; i++) {
			int cost = get<0>(edge[i]);
			int u = get<1>(edge[i]);
			int v = get<2>(edge[i]);

			merge(u, v);

			for (int j = 0; j < check_edge_range[i].size(); j++) {
				int query_number = check_edge_range[i][j]; //간선 i개를 연결했을때 확인하려고 저장해두었던 쿼리

				//x와 y가 연결되어 있는지 확인
				int x = query[query_number].first;
				int y = query[query_number].second;

				//x와 y가 연결이 될때
				if (find(x) == find(y)) {
					result[query_number] = make_pair(cost, group_size[find(x)]);
					query_range[query_number].second = i - 1;
				}

				else {
					query_range[query_number].first = i + 1;
				}
			}
		}

	}

	for (int i = 0; i < q; i++) {
		if (result[i].first == -1) {
			cout << -1 << "\n";
		}

		else {
			cout << result[i].first << " " << result[i].second << "\n";
		}
	}


	return 0;
}