[백준] 13306 트리

 

각 정점 v에서 루트 r과 연결하는 유일한 경로 P에 대해서 정점 v와 에지로 연결된 정점 중에서 P상에 있는 정점을 v의 ‘부모 정점’이라고 한다. → 정점 v에서 루트 노드로 가는 경로에 포함되는 간선중에, 정점 v와 연결된 간선 반대편에 있는 노드를 부모 노드라고 함. 즉, 루트노드 - 정점 v 사이에 있는 v 인접 노드를 의미함.

 

트리 T에서 어떤 두 정점을 연결하는 에지를 제거하면 그 두 정점 외에도 경로가 존재하지 않는 정점 쌍이 있을 수 있다. 여러분은 “정점 v와 w를 연결하는 경로가 존재하는가?”와 같은 질의에 답해야 한다. 예를 들어, 그림 1에서 7과 11 사이의 에지를 제거하면 8과 5를 연결하는 경로는 존재하지 않는다. 트리 정보가 주어지고, 에지의 제거 정보와 질의가 임의의 순서로 주어질 때, 작업을 순서대로 수행하며 질의에 대한 답을 출력하는 프로그램을 작성하시오. → (1) 트리의 간선을 제거하는 행동. (2) 노드 2개가 서로 이어져있는지 확인하는 행동 = 노드 2개를 잇는 경로가 존재하는지 확인하는 행동(union-find).

 

근데 이때 union-find(+path compression)을 이용하면 나중에 간선이 끊어졌을 때 그에 영향을 받는 노드들의 parent를 수정하는데 시간이 걸리게 된다. & 하나에서 자르는 것보다, 잘라진것에서 합치는것이 더 쉬워보임. 따라서 받은 쿼리를 거꾸로 실행하여, 간선이 모두 연결되어있지 않은 상태에서 하나씩 연결하고, 연결성을 확인하는 방식으로 한다.

 

 

 

 

 

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

int N, Q, a, b, x;
int parent[MAX_NQ];
pair<int, pair<int, int>> query[MAX_NQ*2];
stack<bool> ans;

int find_parent(int c) {
    if (parent[c] == c) return c;
    else return parent[c] = find_parent(parent[c]);
}

void union_find(int a, int b) {
    int ap = find_parent(a);
    int bp = find_parent(b);

    if (ap < bp) parent[bp] = ap;
    else parent[ap] = bp;
}

bool is_unions(int a, int b) {
    int ap = find_parent(a);
    int bp = find_parent(b);

    return ap == bp;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> Q;

    parent[1] = 1;
    for (int i = 2; i <= N; ++i) {
        cin >> a;
        parent[i] = a;
    }

    for (int i = 0; i < N+Q-1; ++i) {
        cin >> x;
        if (x) {
            cin >> a >> b;
            query[i] = {1, {a, b}};
        }
        else {
            cin >> a;
            query[i] = {0, {a, parent[a]}};
            parent[a] = a;
        }
    }

    for (int i = N+Q-2; i >= 0; --i) {
        if (query[i].first) { // 연결 확인
            ans.push(is_unions(query[i].second.first, query[i].second.second));
        }
        else {
            union_find(query[i].second.first, query[i].second.second);
        }
    }

    while (!ans.empty()) {
        cout << (ans.top() ? "YES\n" : "NO\n");
        ans.pop();
    }
    return 0;
}