[BOJ 2843] 마블

Problem

민혁이는 매주 금요일마다 지수와 함께 논다. 이번 주 금요일은 지수와 민혁이가 친구가 된지 십 년이 되는 날이다. 따라서, 둘은 엄청난 게임을 하기로 결정했다. 민혁이는 바닥이 흙인 운동장을 예약했고, 지수는 조약돌 한 개를 들고 왔다.

먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(outgoing edge)를 가질 수 있다. 그 다음 민혁이는 조약돌을 한 정점 위에 올려 놓는다. 만약, 조약돌이 있는 정점에 나가는 간선이 있다면, 조약돌은 그 간선을 통해서 이동할 수 없을 때까지 계속해서 이동한다. 더 이상 이동할 수 있는 정점이 없다면, 조약돌은 그 자리에서 멈춘다. 조약돌은 그래프를 무한히 이동할 수도 있고, 방문하지 않는 정점이 있을 수도 있다.

민혁이는 지수가 게임의 규칙을 확실하게 이해했는지 알기 위해서 다음과 같은 두 가지 질문을 하려고 한다.

• 1 X - 조약돌을 정점 X에 놓았을 때, 조약돌이 무한히 움직이지 않는다면 조약돌이 멈추는 정점의 번호는 몇 번인가?
• 2 X - 정점 X에서 나가는 간선을 지운다. (항상 나가는 간선이 있는 정점만 주어진다)

민혁이의 질문이 주어졌을 때, 지수의 답변을 출력하는 프로그램을 작성하시오.

Solution Part I

핵심은 어떤 정점 X에서 나가는 간선을 지우는 option 밖에 없음이 있다.

즉, 문제에서의 상황을 directed graph로 표현할 시, edge를 추가하는 조건 말고 제거하는 조건 뿐이라는 것으로 해석할 수 있다. 또한, cycle이 없는 경우에는 graph가 아닌 Tree로 표현이 가능하다는 점도 있다.

따라서 cycle이 없다는 가정하에 Tree로 생각하고 문제를 해결한 후, 반복이 들어가는 경우를 따로 처리해주자.

또한, 1번 질의는 트리 상에서 해당 node의 leaf node가 무엇이냐?로 해석할 수 있고, outgoing edge가 하나뿐이므로 이는 유일하게 결정이 된다.

즉, 결국 우리가 알아야 하는 것은

1. 어떤 node가 있을 때 leaf node를 빠르게 결정하는 방법
2. 노드의 제거 연산을 빠르게 하는 방법

이다.

Solution Part II

이처럼 leaf node(또는 root node)를 빠르게 찾는 방법은 Union-find 자료 구조로 해결할 수 있다.

다만, Union-find에서 제거 연산을 하기 위해서는 Path compression를 포기해야 하므로 시간 복잡도에서 굉장히 큰 손해를 본다.

따라서 제거 연산을 다른 방법을 활용하여 해결해야 하는데, 제거의 역은 추가임을 이용하자.

즉, q번째 쿼리에서 Node 3의 outgoing edge를 없애는 것은 (이전 q-1번째 까지 3번 edge O) => (q번째 제거) => (이후 끝까지 3번 edge X)이므로 쿼리를 역으로 처리하여 (Q ~ q+1번째까지 3번 Edge X) => (q번째 추가) => (q-1번째부터 1번째까지 3번 Edge O)로 생각하자.

그러면, 제거 연산이 추가 연산으로 바뀌기 때문에 Path Compression을 적용하여 시간 복잡도에서 큰 이득을 볼 수 있다.

따라서 모든 쿼리를 미리 입력 받은 다음 끝에서부터 query를 차례차례 해결해주자.

이때, 초기 그래프가 주어지고 여기에서 간선이 계속 제거되는 상황을 뒤집어서 Edge를 추가하는 것(Union)으로 처리하는 경우이므로, 본격적으로 쿼리를 처리하기 전에 추가 되는 모든 Edge를 없애주어야 한다.

Solution Part III

마지막으로 cycle이 생기는 경우를 처리해야한다.

먼저 한번 cycle이 생기면 Edge를 제거하는 연산은 존재하지 않기 때문에 그 안에 있는 모든 node들의 출력은 "CIKLUS"로 고정이다.

따라서 이런 경우에는 아래 그림처럼 cycle 내의 아무 정점을 기준으로 모두 그 정점으로 부모를 보내고, 이 부모를 가르키게 될 경우 CIKLUS를 출력하게 된다.

이러한 cycle을 체크하는 경우는 쿼리를 처리하기 전에 전처리로 처리해주면 되고, 이후에는 merge 작업을 수행하면서 만약 두 노드가 같은 부모를 공유하면 이미 path가 있다는 것이고, 그러면 cycle이 존재하는 것이므로 다른 배열에 기록해두면 된다.

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
 
bool chk[300006];
int tmp[300006], cnt = 1;
int par[300006];
stack<pii> qry;
stack<int> add, ans;
 
int init(int x, int cnt) {
    tmp[x] = cnt;
    if (tmp[par[x]] == cnt && par[x] != x) chk[par[x]] = true;
    return tmp[par[x]] ? par[x] : (par[x] = init(par[x], cnt));
}
 
int fin(int x) { return (par[x] == x) ? par[x] : (par[x] = fin(par[x])); }
 
// x -> y 추가
void merge(int x, int y) {
    x = fin(x);
    y = fin(y);
    if (x == y)
        chk[x] = true;
    else
        par[x] = y;
}
 
int main() {
    int n, q;
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        par[i] = (x ? x : i);
    }
    scanf("%d", &q);
    while (q--) {
        int op, num;
        scanf("%d %d", &op, &num);
        qry.push({op, num});
        if (op == 2) add.push(par[num]), par[num] = num;
    }
    for (int i = 1; i <= n; i++) if (!tmp[i]) init(i, cnt++);
    while (!qry.empty()) {
        auto p = qry.top();
        qry.pop();
        if (p.first == 1) {
            int t = fin(p.second);
            ans.push((chk[t] ? -1 : t));
        } else {
            int ad = add.top();
            add.pop();
            merge(p.second, ad);
        }
    }
    while (!ans.empty()) ans.top() == -1 ? puts("CIKLUS") : printf("%d\n", ans.top()), ans.pop();
    return 0;
}