본문 바로가기

Problem Solving/문제풀이

[CF] 100551A Connect and Disconnect


  • 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다.

  • 문제 풀이: 
- 쿼리가 오직 + 와 ?만 들어온다면...?
Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다.

- 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?
Union-Find Tree를 그대로 첫번째 풀이에 적용할 수 있을까? 아쉽게도 그럴 수 없다. Union-Find Tree는 임의로 두 집합을 분리킬 수 없다는 치명적인 약점이 있으므로 합치는 걸 빠르게 할 수 없다! 어쩔 수 없이 각 간선을 추가/제거한 뒤 직접 dfs를 수행하면서 컴포넌트 개수를 확인할수 밖에 없다. 이때 시간복잡도는 $O(k(n+k))$이다.

- 그러면 Union-Find Tree를 써볼 수 있는 방법이 없을까...?
합치는 연산은 매우 빠르게 할 수 있음을 이미 알고 있다. 그런데 생각을 해볼 수 있는 것은 Union-Find Tree에서 간선을 추가했다가 바로 전 상태로 되돌리는 Undo 연산은 당연하지만 상수 시간에 수행할 수 있다는 점이다. (이를 위해서는 Path Compression을 포기하는게 낫다. 어차피 Rank-By-Optimization만 해줘도 로그 시간복잡도가 보장된다.) 그러면 어떤 간선이 추가될 때 Union을 했다가 삭제 쿼리가 들어오면 추가 쿼리가 들어올 때까지 Undo한 다음 그 쿼리만 빼고 다시 다 Union 해주면 되는 것이지 않은가. 이 아이디어를 사용하면 Union-Find를 사용할 수 있는데, 문제는 합치는 연산과 삭제 연산이 멀리 떨어져 있을 경우 최악의 경우에 $O(k^2 lgn)$이다. 너무 느리다.

- 어떻게 더 빠르게 할 수 있는 방법이 없을까?
굳이 모든 경우에 대해서 처음으로 되돌아 갈 때까지 Undo할 필요가 없다! 다음과 같이 생각해보자. 매 간선마다 그 간선이 존재하는 시간이 (le,ri)꼴로 기록되어 있다고 하자. 이때 le와 ri는 '?' 쿼리 번호이다. 그리고 다음과 같이 분할 정복을 사용한다.

F(st, en): st번째 ? 쿼리부터 en번째 ? 쿼리까지 답을 출력.

만약 F(st,en)이 st부터 en까지 항상 존재하는 간선들의 집합을 유지한다고 하자. 그러면 이를 절반으로 쪼갤 때는 F(st,mid)와 F(mid+1,en)이 되는데 이때 각각의 함수를 호출하기 전과 후에 간선들의 집합을 갱신해주어야 한다. 예를 들어 F(st,mid)를 호출할 때에는 st부터 mid까지 항상 존재하는 간선을 추가적으로 union해주어야 하고, 종료하고 나서는 union 해주었던 간선을 모두 undo 해주어야 한다. st와 en이 같을 때만 결과를 출력해주면 된다.
다음과 같이 생각하면 쉽다. 어떤 세그먼트 트리를 하나 구축해서 간선이 존재하는 시간을 덮는 세그먼트 트리의 각 노드에 간선을 기록한다. 그러면 간선 하나가 최대 $O(log k)$개의 노드에 담기게 된다. 그 후 세그먼트 트리에서 DFS를 수행한다. 이 과정은 위 분할 정복과 정확히 같은 과정을 수행한다. 각 함수가 호출될 때 마다 그 노드에 담긴 간선을 모두 union 해 주고, 그 함수가 종료하기 전에 undo를 사용해 원 상태로 복구해 준다. 이렇게 하면 각 간선이 $O(lg k)$번 union되고 삭제되므로 총 시간복잡도는 $O(k lg k)$가 된다. 

  • 소스 코드
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
 
using namespace std;
typedef pair<int,int> pii;
typedef vector<pii> vp;
typedef vector<int> vi;
 
typedef struct DSU{
    vector<int> par,ra;
    int s;
    DSU(int _n) : par(_n+1), ra(_n+1), s(0){
        for(int i=0;i<=_n;i++) par[i]=i;
    }
    int fi(int x){
        while(par[x]!=x) x=par[x];
        return x;
    }
    pii un(int a, int b){
        a=fi(a); b=fi(b);
        if(a==b) return mp(-1,-1);
        if(ra[a]>ra[b]) swap(a,b);
        par[a]=b;
        if(ra[a]==ra[b]) ra[b]++;
        s++;
        return mp(a,b); //a를 b에 합쳤음
    }
    void undo(int a, int b){
        par[a]=a;
        if(ra[b]==ra[a]+1) ra[b]--;
        s--;
    }
}DSU;
 
int n,q;
vector<vp> tree;
DSU uf(300005);
 
void update(int node, int st, int en, int le, int ri, pii e){
    if(ri<st || en<le) return;
    if(le<=st && en<=ri){
        tree[node].pb(e);
        return;
    }
    int mid=(st+en)>>1;
    update(node*2,st,mid,le,ri,e);
    update(node*2+1,mid+1,en,le,ri,e);
}
 
void dfs(int node, int st, int en){
    vector<pii> tv;
    for(pii k : tree[node]){
        tv.push_back(uf.un(k.first,k.second));
    }
    if(st!=en){
        int mid=(st+en)>>1;
        dfs(node*2,st,mid);
        dfs(node*2+1,mid+1,en);
    }
    else{
        printf("%d\n",n-uf.s);
    }
    while(!tv.empty()){
        pii k=tv.back(); tv.pop_back();
        if(k.first==-1continue;
        uf.undo(k.first,k.second);
    }
}
 
map<pii, int> M;
vector<pair<pii,pii> > query;
 
int main(){
    freopen("connect.in","r",stdin);
    freopen("connect.out","w",stdout);
    scanf("%d %d",&n,&q);
 
    int time=1;
    for(int i=1;i<=q;i++){
        char sel;
        int t1,t2;
        scanf(" %c",&sel);
        if(sel=='?') time++;
        else if(sel=='+' || sel=='-'){
            scanf("%d %d",&t1,&t2);
            if(t1>t2) swap(t1,t2);
            if(M[mp(t1,t2)]){
                query.emplace_back(mp(t1,t2),mp(M[mp(t1,t2)],time));
                M[mp(t1,t2)]=0;
            } 
            else M[mp(t1,t2)]=time;
        }
    }
    if(time==1return 0;
    for(auto it : M){
        if(it.second)
            query.emplace_back(it.first,mp(it.second,time));
    }
    tree.assign(5*(time+2),vp());
    for(auto k : query){
        pii idx=k.first;
        pii life=k.second; life.second--;
        if(life.second<life.first) continue;
        update(1,1,time-1,life.first,life.second,idx);
    }
    dfs(1,1,time-1);
    return 0;
}
 
cs


'Problem Solving > 문제풀이' 카테고리의 다른 글

USACO 2020 January (Gold) 풀이  (2) 2020.01.22
[BOJ] 13309 트리  (1) 2019.05.27
[USACO] 2018 January Contest (Silver) 풀이  (0) 2018.11.06
[BOJ] 10067 수열 나누기  (0) 2018.10.29
[BOJ] 1693 트리 색칠하기  (0) 2018.10.22