Baekjoon 13306 트리

Link https://www.acmicpc.net/problem/13306

소스결과 10180 KB / 132 ms

출처 Baekjoon, KOI 2016 중등부

언어 C++ 17

분류 Disjoint-Set

 

설명

그래프의 정보가 주어지고, 그래프의 일부 내용이 변경 되었을 때 주어지는 질의에 대해서 답을 출력해주는 프로그램을 작성한다.

 

여태껏 문제와는 문제를 보는 방식이 조금 달랐던 문제. 좋은 내용을 배웠다.

주어지는 질의에 대해서 질의를 역순으로 해결해 나가면서 정답은 질의 순으로 제출하는 방법이다.

결과적으로 질의가 시작되기 전의 그래프는 주어진 그래프의 모습일테니 거꾸로 생각해서 풀어도 문제가 없다. 출력만 유의하면 될 뿐

Disjoint-Set의 기본 골격을 유지하고 질의를 거꾸로 풀어나가보자

 

스터디에서 배워가는 내용 이기에 Disjoint-Set은 Class화 시켜 사용했다.

 

소스코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct Question {
	int order;
	int x, y;
};

class DisJointSet
{
	int size;
	vector<int> parent;

public:
	DisJointSet(int size) : size(size) {
		parent.resize(size);
		for (int i = 0; i < size; i++) parent[i] = i;
	};

	int find(int v) {
		if (parent[v] == v) return v;

		return parent[v] = find(parent[v]);
	}
	bool merge(int x, int y) {

		int px = find(x);
		int py = find(y);

		if (px == py)
			return false;

		parent[px] = py;

		return true;
	}
};

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

	int n, q;
	cin >> n >> q;

	DisJointSet dis(n + 1);
	vector<Question> queries(n-1+q);
	vector<int> res;
	vector<int> p(n + 1);

	for (int i = 2; i <= n; i++) {
		cin >> p[i];
	}

	for (int i = 0; i < n - 1 + q; i++)
	{
		cin >> queries[i].order;
		if (queries[i].order)
			cin >> queries[i].x >> queries[i].y;
		else
			cin >> queries[i].x;
	}

	for (int i = n - 1 + q - 1; i >= 0; i--) {
		if (queries[i].order) {
			if (dis.find(queries[i].x) == dis.find(queries[i].y))
				res.push_back(1);
			else
				res.push_back(0);
		}
		else
			dis.merge(queries[i].x, p[queries[i].x]);
	}

	for (int i = q - 1; i >= 0; i--)
		cout << (res[i] ? "YES" : "NO") << '\n';

	return 0;
}