백준 13306번: 트리 (C++)

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

13306번: 트리

---

Solved By: Offline Query, Union-Find

 

문제를 직관적으로 처리하려면 DFS를 하는데에 있어서 쿼리의 개수까지 고려하면 O(NQ)로 시간 초과가 나옵니다.

 

하지만, 쿼리를 우리에게 유리하게끔 쿼리 순서를 바꾸어 Offline Query로 처리하려 한다면 문제에서 '간선을 끊어라'는 '간선을 이어라'가 되면서 Union-Find 문제가 됩니다. -> O(QlogN)

 

그리고, 쿼리에서 간선을 끊는 쿼리는 총 N-1개가 주어진다 하였으므로 Offline Query의 관점에서 문제를 본다면 Edge 하나도 없는 그래프에서 Edge를 이어가며 두 노드 사이에 경로가 있는지만 확인하면 됩니다.

#include <iostream>
#include <vector>
#include <stack>
#define MAX 200001
using namespace std;

int N, Q;
int query[2 * MAX][3];
int parent[MAX];
int uf[MAX];

int getRoot(int node){
    if(uf[node] < 0) return node;
    else return uf[node] = getRoot(uf[node]);
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) uf[gb] = ga;
    else uf[ga] = gb;
}

int main(){
    cin >> N >> Q;
    for(int i = 2; i < N + 1; i++){
        cin >> parent[i];
    }
    
    Q += N - 1;
    for(int i = 0; i < Q; i++){
        cin >> query[i][0] >> query[i][1];
        if(query[i][0] == 1) cin >> query[i][2];
    }
    
    // Query를 거꾸로 유리하게 처리 => Offline Query
    stack<bool> res;
    fill(uf, uf + MAX, -1);
    for(int i = Q - 1; i >= 0; i--){
        if(!query[i][0]) unionNodes(query[i][1], parent[query[i][1]]);
        else{
            int u = getRoot(query[i][1]), v = getRoot(query[i][2]);
            res.push(u == v);
        }
    }
    
    while(!res.empty()){
        cout << (res.top() ? "YES" : "NO") << '\n';
        res.pop();
    }
    
    return 0;
}