[백준BOJ] 13306 트리

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

13306번: 트리

---

문제해설

이 문제의 아이디어는 설렁설렁 문제를 읽어서는 떠오르기 쉽지 않은 문제입니다.

이 문제는 disjoint-set 및 union-find 알고리즘을 사용한다는 것 까지는 쉽게 알 수 있습니다.

그러나 union-find 의연산횟수가 적은 이유는

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return par[x] = find(par[x]);
}

위 처럼, find를 할때에 union의 root를 부모로 설정해주기 때문입니다.

 

그러나,

이문제에서는 자신의 바로 윗부모와의 엣지를 삭제하는 쿼리가 들어옵니다.

위의 코드가 전혀 쓸모없는 코드가 되어버리고

저코드를 활용한다하더라도

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return find(par[x]);
}

위 처럼, 딱봐도 TL이 걸릴 것 같은 코드정도로 밖에 쓰지 못할 것입니다.

 

union-find의 특성을 그대로 활용하기 위해서

쿼리를 뒤에서부터 처리해주는 방법을 선택할 수 있습니다.

제일 뒤에서부터 시작하기 때문에, 아무런 연결이 없는상태로 시작해서

삭제되는 쿼리를 만나면 union을 시켜주는 형태로 문제를 풀어 나가면 됩니다.

---

전체코드

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

class Input {
public:
	int tag, x, y, par;
	Input() {};
	Input(int tag, int x, int y) {
		this->tag = tag;
		this->x = x;
		this->y = y;
	}
	Input(int tag, int x) {
		this->tag = tag;
		this->x = x;
	}
};

int par[200001];
int origin[200001];
vector<string> ans;
vector<Input> input;

int find(int x) {
	if (par[x] == x) {
		return x;
	}
	return par[x] = find(par[x]);
}

void make_set(int x, int p) {
	x = find(x);
	p = find(p);
	par[x] = p;
	//cout << x << "의부모 : " << par[x] << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, Q;
	cin >> N >> Q;
	par[1] = 1;
	for (int i = 2; i <= N; i++) {
		cin >> origin[i];
		par[i] = i;
	}


	for (int i = 0; i < N + Q - 1; i++) {
		int tag;  cin >> tag;
		if (tag) {
			int x, y; cin >> x >> y;
			input.push_back(Input(1, x, y));
		}
		else {
			int x; cin >> x;
			input.push_back(Input(0, x));
		}
	}

	vector <string> ans;
	for (int i = N + Q - 2; i >= 0; i--) {
		if (input[i].tag) {
			int x = input[i].x;
			int y = input[i].y;
			if (find(x) == find(y)) ans.push_back("YES");
			else ans.push_back("NO");
		}
		else {
			int x = input[i].x;
			make_set(x, origin[x]);
		}
	}

	for (int i = Q - 1; i >= 0; i--) {
		cout << ans[i] << "\n";
	}
}