코드 복사/붙여넣기 하는 당신이 아름답습니다.

13306 : 트리

풀이

엣지를 제거하면서 union find를 하려면 TLE가 난다.

문제를 거꾸로 생각하자.

원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다.

그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?!

간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다.

발상의 전환이 조금 어려운 문제인 것 같다.

코드

#include <bits/stdc++.h>
using namespace std;

const int n_ = 2e5 + 3;

int n, q;
int gph[n_], pnt[n_], q1[n_ * 2], q2[n_ * 2];
stack<bool> ans;

inline int find(int u) {
	if (u == pnt[u]) return u;
	return pnt[u] = find(pnt[u]);
}

inline void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u > v) swap(u, v);
	if (u == v) return;
	pnt[u] = v;
}

int main() {
	int i, a;
	scanf("%d %d", &n, &q);
	for (i = 2; i <= n; i++) {
		scanf("%d", &a);
		gph[i] = a;
		pnt[i] = i;
	} gph[1] = 1;
	for (i = 1; i <= n + q - 1; i++) {
		scanf("%d", &a);
		if (a) scanf("%d %d", &q1[i], &q2[i]);
		else scanf("%d", &q1[i]);
	}
	for (i = n + q - 1; i; i--) {
		if (q2[i]) {
			if (find(q1[i]) == find(q2[i])) ans.push(1);
			else ans.push(0);
		}
		else {
			merge(q1[i], gph[q1[i]]);
		}
	}
	while (!ans.empty()) {
		ans.top() ? puts("YES") : puts("NO"); ans.pop();
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-04-10 11:46

Read more posts by this author