[백준/BOJ] 백준 2843번 : 마블

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

2843번: 마블

쿼리의 순서를 거꾸로 처리하기 위해 쿼리를 미리 저장해 놓는 오프라인 쿼리를 이용해 문제를 해결했다. 쿼리를 거꾸로 처리하면 간선을 지우는 쿼리에 의해 지워질 간선은 미리 지워놓고, 간선을 지우는 쿼리에서 해당 간선을 연결하는 방식으로 문제를 해결할 수 있기 때문이다. 간선의 연결은 유니온 파인드를 이용했고, 이를 통해 해당 그룹의 사이클은 판단했다

 

코드

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

int n;
int q;
vector<int> parent(300001, 0);
vector<int> out_edge(300001, 0);
vector<int> disconnected(300001, 0);
vector<int> cycle(300001, 0);
vector<pair<int, int>> query;
vector<string> output;

void Pre()
{
	for (int i = 0; i < 300001; i++)
	{
		parent[i] = i;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

//u를 v쪽으로 합친다
void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	//해당 연결로 싸이클이 생길때
	if (u == v)
	{
		cycle[u] = 1;
		return;
	}

	//연결하는 쪽이 싸이클이 있을때
	else if (cycle[v] == 1)
	{
		cycle[u] = 1;
		return;
	}

	parent[u] = v;
}

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

	Pre();

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		out_edge[i] = input;
	}

	cin >> q;

	for (int i = 0; i < q; i++)
	{
		int order, x;

		cin >> order >> x;

		if (order == 2)
		{
			//간선을 지우는 쿼리가 있다면 일단 해당 간선을 끊어 놓는다
			disconnected[x] = 1;
		}

		//쿼리를 거꾸로 해서 문제를 해결하기 위해 저장해 놓는다
		//쿼리를 거꾸로 문제를 해결하면, 이전에 간선을 지우는 쿼리의 간선은 미리 끊어놓는것으로 체크해 놨으므로
		//거꾸로 쿼리를 가져올때 간선을 지우는 쿼리에서 해당 연결을 하는 방식으로 문제를 해결한다
		query.push_back(make_pair(order, x));
	}

	//disconnected가 1로 체크된것을 제외한 나머지를 연결한다
	for (int i = 1; i <= n; i++)
	{
		//i에서 나가는 간선이 없을때
		if (out_edge[i] == 0)
			continue;

		//i에서 나가는 간선이 끊어졌을때
		if (disconnected[i] == 1)
			continue;

		Merge(i, out_edge[i]);
	}

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

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

		//x에서 나가는 간선을 연결한다
		if (order == 2)
		{
			Merge(x, out_edge[x]);
		}

		else
		{
			int u = Find(x);

			if (cycle[u] == 1)
				output.push_back("CIKLUS");

			else
				output.push_back(to_string(u));
		}

	}

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

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

	return 0;
}