백준2843 마블

작성일 | In

문제 링크

  • http://icpc.me/2843

문제 출처

  • 2010/2011 COCI #7 5번

사용 알고리즘

  • Union Find
  • Offline Query

시간복잡도

  • O(N + Q alpha N)

풀이

간선을 지우는 쿼리가 주어지면, 일단 오프라인을 의심해봐야 합니다.
쿼리를 역순으로 처리해주면 간선을 만드는 쿼리로 바뀌기 때문에 union find로 처리해줄 수 있습니다.

merge를 해줄 때, 이미 같은 집합에 있는 두 정점을 merge하면 사이클이 생기므로 적절히 처리해주면 쉽게 풀 수 있습니다.

이런 방식으로 풀리는 문제로는 BOJ13306 트리, BOJ17469 트리의 색깔과 쿼리 등이 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int par[1010101];
int find(int v){
    return v == par[v] ? v: par[v] = find(par[v]);
}
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) par[u] = par[v] = 0;
    else par[u] = v;
}

int n, q, pv;
int nxt[1010101];
int chk[1010101];
vector<p> qry;
int ans[1010101];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++) par[i] = i, cin >> nxt[i];
    cin >> q; qry.resize(q+1);
    for(int i=1; i<=q; i++){
        cin >> qry[i].x >> qry[i].y;
        if(qry[i].x == 2) chk[qry[i].y] = 1;
    }
    for(int i=1; i<=n; i++){
        if(!chk[i] && nxt[i]) merge(i, nxt[i]);
    }
    for(int i=q; i>=1; i--){
        if(qry[i].x == 1){
            ans[++pv] = find(qry[i].y);
        }else{
            merge(qry[i].y, nxt[qry[i].y]);
        }
    }
    for(int i=pv; i>=1; i--){
        if(!ans[i]) cout << "CIKLUS\n";
        else cout << ans[i] << "\n";
    }
}