2843 - 마블

문제 링크

---

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

문제 요약

---

\(N\)개의 정점가 \(N\)개의 간선을 가지는 방향그래프가 주어진다. 각각의 정점은 최대 한개의 나가는 간선을 가질 수 있다. 이 때 두 가지의 쿼리를 처리해야 한다. 첫 번재 쿼리는 \(x\)번 정점에서 나가는 간선을 지우는 것이도 두 번째 쿼리는 \(x\)번 정점에서 나가는 간선을 따라 계속해서 움직일 때 마지막으로 도착하는 정점이 어디인지, 만약 영원히 끝나지 않는다면 영원히 끝나지 않는다고 출력을 해야 한다.

문제 풀이

---

연결된 그래프에서 간선을 지워서 두개의 분리된 그래프로 만드는 작업은 생각보다 어려운 일이다. 하지만 반대로 두개의 분리된 그래프를 하나로 합쳐 새로운 그래프를 만드는 작업은 꽤 쉬운 일이다. 이와같은 작업은 \(disjoint\ set\)을 통해 매우 빠른 속도로 진행할 수 있다.

그렇다면 우리는 쿼리을 온라인으로 처리하는 것이 아니라 오프라인으로 처리하면 문제를 푸는것이 더 쉬워진다고 생각할 수 잇다. 쿼리를 처음부터 생각하는 것이 아니라 거꾸로 생각해 나간다면 간선을 지우는 것이 아니라 새로운 간선을 추가하는 것이 되고 이는 위에서 말한 두 개의 그래프를 하나의 그래프로 합치는 작업이 된다. 해당 그룹에서 계속해서 움직이면 최종적으로 어디에 도착하는지 유지를 해 주며 \(merge\)할 때 이를 갱신시켜 준다면 문제를 쉽게 해결할 수 있다.

주의 사항으로 방향그래프 이기 때문에 \(merge\)를 할 때 방향을 잘 생각해서 마지막에 도착하는 점을 갱신해 줘야 한다는 것이다. \(Union\ find\)를 사용한다면 \(O(N + Q)\)에 문제를 해결할 수 있다.

소스 코드

---

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 300010;
int n, m, out[MAX], erase[MAX], QA[MAX], QB[MAX], ans[MAX];

struct Union {
  vector<int> p, r, last;
  Union(int n) : p(n), r(n, 1), last(n) {
    for (int i = 0 ; i < n ; ++i) {
      p[i] = last[i] = i;
    }
  }
  int find(int u) {
    if (u == p[u]) {
      return u;
    }
    return p[u] = find(p[u]);
  }
  void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) {
      last[u] = -1;
      return;
    }
    
    int newLast = last[v];
    if (r[u] > r[v]) {
      swap(u, v);
    }
    p[u] = v;
    last[v] = newLast;
    if (r[u] == r[v]) {
      ++r[v];
    }
  }
  int getLast(int u) {
    return last[find(u)];
  }
};

int main() {
  scanf("%d", &n);
  for (int i = 1 ; i <= n ; ++i) {
    scanf("%d", &out[i]);
  }
  scanf("%d", &m);
  for (int i = 0 ; i < m ; ++i) {
    scanf("%d%d", &QA[i], &QB[i]);
    if (QA[i] == 2) {
      erase[QB[i]] = 1;
    }
  }
  
  Union uni(n + 1);
  for (int i = 1 ; i <= n ; ++i) {
    if (!erase[i] && out[i]) {
      uni.merge(i, out[i]);
    }
  }
  
  for (int i = m - 1 ; i >= 0 ; --i) {
    if (QA[i] == 1) {
      ans[i] = uni.getLast(QB[i]);
    } else if (QA[i] == 2 && out[QB[i]]){
      uni.merge(QB[i], out[QB[i]]);
    }
  }
  
  for (int i = 0 ; i < m ; ++i) {
    if (ans[i]) {
      if (ans[i] == -1) {
        puts("CIKLUS");
      } else {
        printf("%d\n", ans[i]);
      }
    }
  }
}