[백준/BOJ] 백준 20930번 : 우주 정거장

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

20930번: 우주 정거장

선분에 대한 정보를 x좌표에 대한 정보, y좌표에 대한 정보를 나누어서 정렬한 뒤 인접한 선분들과 이동할 수 있으면 유니온 파인드의 유니온을 하는 방법을 통해 문제를 해결했다.

 

코드

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

int n, q;
vector<pair<pair<int, int>, int>> x_info; //((x1, x2),정거장 번호)
vector<pair<pair<int, int>, int>> y_info; //((y1, y2),정거장 번호)
vector<int> parent(200001);
vector<int> rank_size(200001, 1);

void Pre()
{
	for (int i = 1; i <= 200000; 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;
	}

	else
	{
		parent[v] = u;

		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 = 1; i <= n; i++)
	{
		int x1, y1, x2, y2;

		cin >> x1 >> y1 >> x2 >> y2;

		x_info.push_back(make_pair(make_pair(min(x1, x2), max(x1, x2)), i));
		y_info.push_back(make_pair(make_pair(min(y1, y2), max(y1, y2)), i));
	}

	sort(x_info.begin(), x_info.end());
	sort(y_info.begin(), y_info.end());

	for (int i = 1; i < x_info.size(); i++)
	{
		pair<pair<int, int>, int> before_x_info = x_info[i - 1];
		pair<pair<int, int>, int> here_x_info = x_info[i];

		if (before_x_info.first.second >= here_x_info.first.first)
		{
			Merge(before_x_info.second, here_x_info.second);
		}
	}

	for (int i = 1; i < y_info.size(); i++)
	{
		pair<pair<int, int>, int> before_y_info = y_info[i - 1];
		pair<pair<int, int>, int> here_y_info = y_info[i];

		if (before_y_info.first.second >= here_y_info.first.first)
		{
			Merge(before_y_info.second, here_y_info.second);
		}
	}

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

		if (Find(u) == Find(v))
			cout << 1 << "\n";
		else
			cout << 0 << "\n";
	}

	return 0;
}