풀이
엣지를 제거하면서 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이