Online Dynamic Connectivity (동적 연결성 문제 온라인으로 풀기)

Dynamic Connectivity Problem(동적 연결성 문제)란, 다음과 같은 쿼리를 처리하는 문제를 말합니다.

• 임의의 간선 추가
• 임의의 간선 삭제
• 어떤 두 정점 사이에 경로가 존재하는지 판별

이 문제는 분할 정복을 통해 오프라인으로 풀 수 있지만, 이 글에서는 온라인 풀이를 설명합니다.

 

그래프가 포레스트일 때

포레스트에서는 Link-Cut Tree나 Euler Tour Tree를 사용하여 풀 수 있습니다. 이번에는 Euler Tour Tree를 사용합니다.

 

어떤 트리를 Euler Tour로 나타낸 수열에서 그 트리를 복원할 수 있기 때문에 각 트리를 트리 자체가 아닌 Euler Tour로 관리합니다.

 

 

이렇게 관리하면 간선의 추가, 삭제는 이 수열을 끊고 연결하는 연산들로 대체할 수 있습니다.

 

Euler Tour의 루트 (탐색 시작 정점) 변경

 

• 새 루트로 할려고 하는 정점을 r이라 합시다. (위 그림에서는 e)
• r이 포함된 Euler Tour에서 r을 아무거나 잡고 r의 왼쪽을 끊습니다. 이 때 왼쪽 수열을 A, 오른쪽 수열을 B라 합시다.
• A의 가장 왼쪽(또는 B의 가장 오른쪽) 수를 제거하고, B의 오른쪽에 A를 연결합니다.
• 연결된 수열의 가장 오른쪽에 r을 추가합니다.

간선 연결

• 연결하려는 간선이 잇는 두 정점을 u, v라 합시다. (위 그림에서는 a, f)
• u와 v를 Euler Tour의 루트로 만듭니다.
• u가 포함된 수열의 오른쪽에 v가 포함된 수열를 연결합니다.
• 연결된 수열의 가장 오른쪽에 u을 추가합니다.

간선 제거

• 제거하려는 간선이 잇는 두 정점을 u, v라 합시다. (위 그림에서는 d, e)
• (u, v)와 (v, u)를 기준으로 Euler Tour를 세 개로 분할합니다. 분할된 수열을 순서대로 A, B, C라 합시다.
• A의 가장 오른쪽 (또는 C의 가장 왼쪽)을 제거하고, A의 오른쪽에 C를 연결합니다.
• 이제 Euler Tour가 AC, B 두개로 분할됩니다.

 

이제 다음과 같은 연산들을 수행할 수 있다면 포레스트에서의 Dynamic Connectivity를 해결할 수 있습니다.

• 어떤 두 수열을 연결
• 어떤 두 수열을 특정 지점에서 분할
• Euler Tour에서 특정 정점의 위치 찾기 (루트 변경에 필요)
• Euler Tour에서 특정 간선의 위치 찾기 (간선 제거에 필요)
• 두 정점이 같은 Euler Tour에 포함되어 있는지 판별

이 연산을을 간단하게 구현하기 위해, Euler Tour를 정점이 아닌 간선들로 표현합니다.

또, 특정 정점의 위치를 찾기 위해 정점 u가 있는 Euler Tour에서 (u, u)와 같은 간선을 하나씩 만들어줍니다.

이제 map과 같은 자료구조를 통해 특정 정점이나 간선의 위치를 빠르게 찾을 수 있습니다. 위에서 설명한 루트 변경, 간선 연결, 간선 제거 연산의 구현이 약간 달라지지만 큰 차이 없이 구현할 수 있습니다.

수열의 연결, 분할과 같은 수열에 있는지 판별하는 것은 Euler Tour를 BST(이진 탐색 트리)의 구조를 통해 관리하면 가능합니다. (이 글에서는 가장 간단한 Splay tree를 사용합니다.)

이제 포레스트에서의 Dynamic Connectivity를 쿼리당 \(O(lgN)\)에 해결할 수 있습니다.

일반적인 그래프에서의 Dynamic Connectivity

그래프가 포레스트가 아니게 되면 그래프 전체를 Euler Tour로 관리할 수 없게 됩니다. 하지만 각 그래프의 스패닝 트리들만을 관리해도 연결성은 차이가 없기 때문에 스패닝 트리를 Euler Tour로 관리합니다.

이렇게 관리할 경우 문제가 되는 것은 스패닝 트리에 포함된 간선의 제거가 일어날 경우입니다.

제거한 간선이 스패닝 트리에 포함된 간선이라면 분리된 두 트리를 잇는 다른 간선이 존재할 수 있고, 이 '대체 간선'을 빠르게 찾아야 합니다. 이를 위해 각 간선의 레벨을 정의합니다. 레벨이 높을수록 그래프의 더 작은 범위를 가지고 있고, 처음에는 모든 간선의 레벨이 0입니다. 알고리즘은 다음과 같이 작동합니다.

• 레벨이 \(i\) 이상인 간선들로만 이루어진 그래프를 \(G_i\), \(G_i\)의 스패닝 포레스트를 \(F_i\)라 합시다. 모든 \(F_i\)를 Euler Tour로 관리하고, \(F_i\)에 포함되지 않은 간선들은 인접 리스트 등을 통해 따로 관리합니다.
• 이 때 \(F_0 \supseteq F_1 \supseteq F_2 \dots \)를 만족한다고 합시다.
• 연결성 판별과 간선의 연결은 \(G_0\)에서 이루어집니다.
• 포레스트에 포함된 간선의 제거는 다음과 같이 이루어집니다:
  • 간선 (u, v)를 제거했고, 분리된 트리 중 u가 포함된 트리를 \(T_u\), v가 포함된 트리를 \(T_v\)라고 합시다. (일반성을 잃지 않고 \(T_u\)가 \(T_v\)보다 작다고 합시다.)
  • (u, v)의 레벨을 L이라 하면, \(G_L\)이 (u, v)가 포함된 가장 레벨이 높은 (가장 한정된) 그래프입니다. 이 그래프부터 \(G_0\)까지 대체 간선의 탐색을 진행합니다.
  • \(F_0 \supseteq F_1 \supseteq F_2 \dots \)이므로 L보다 큰 레벨의 간선은 대체 간선이 될 수 없습니다. \(G_i\)에서의 대체 간선은 \(G_{i-1}\)에서도 대체 간선이고, \(G_i\)보다 레벨이 큰 그래프에서 대체 간선을 찾지 못했는데 \(G_i\)에서의 대체 간선의 레벨이 \(i\)보다 큰 경우도 있을 수 없습니다. 그러므로 \(G_i\)에서는 레벨 \(i\)의 간선만을 탐색해도 됩니다.
  • \(i = L, L - 1, \dots , 0\)에 대해:
    • \(G_i\)에서 \(T_u\)에 포함된 간선의 레벨을 모두 증가시킵니다. (이로 인해 \(F_{i+1}\)가 미리 구성되어 \(F_0 \supseteq F_1 \supseteq F_2 \dots \)를 만족시킬 수 있습니다.)
    • \(G_i\)에서 적어도 한 정점은 \(T_u\)에 포함되어 있고 \(F_i\)에 포함되어 있지 않은 레벨 \(i\)의 모든 간선 e에 대해:
      • e가 잇는 다른 정점이 \(T_u\)라면 그 간선의 레벨을 1 증가시킵니다. (\(G_{i+1}\)에 간선 추가)
      • e가 잇는 다른 정점이 \(T_v\)라면 그 간선이 대체 간선이므로, 전체 탐색을 종료하고 \(G_i, G_{i-1}, \dots , G_0\)에 그 간선을 추가합니다.

간선의 제거로 인해 간선의 레벨이 올라갈 때, 올라간 레벨에서의 그래프는 크기가 반 이상으로 줄어드므로 각 간선은 최대 \(O(lgN)\)번 레벨이 올라갑니다. 대체 간선을 제외한 간선의 탐색에서 간선의 레벨은 무조건 올라가고, Euler Tour를 통한 간선의 추가, 제거, 연결성 판별은 \(O(lgN)\) 시간에 가능하므로 각 쿼리당 amortized \(O(lg^{2}N)\)에 Dynamic Connectivity 문제를 해결할 수 있습니다.

시간복잡도의 보장을 위해 대체 간선을 탐색할 때 레벨 \(i\)인 간선이 적어도 하나는 인접해 있는 정점만을 탐색해야 합니다. 이는 BST에서 레벨 \(i\)인 간선이 인접해 있는 (u, u)들을 탐색하는 것으로 가능합니다. Splay tree에서는 각 서브트리에서 조건을 만족하는 가장 왼쪽 노드로 가는 포인터(mn이라 합시다.)를 저장하고 있으면 x = root->mn부터 시작하여 splay(x), x = x->r->mn를 반복하여 탐색하는 방식으로 구현할 수 있습니다. 각 정점에서 인접한 간선 중 포레스트에 포함되어 있지 않고 레벨이 \(i\)인 간선의 개수를 관리하여 인접한 레벨 \(i\)의 간선이 있는지를 지속적으로 업데이트해야 합니다.

 

다음은 BOJ 16911 그래프와 쿼리 문제를 online으로 해결한 코드입니다.

 

#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
using namespace std;
 
struct node
{
    node* p, *l, *r, *mn;
    int a, b, size;
    bool f;
    node() : p(nullptr), l(nullptr), r(nullptr), mn(nullptr), a(0), b(0), size(0), f(false) {};
};
 
struct edge
{
    int a, b, k;
    edge() : a(0), b(0), k(0) {};
    edge(int a, int b, int k) : a(a), b(b), k(k) {};
    bool operator<(const edge& r) const {
        if (a != r.a) return a < r.a;
        if (b != r.b) return b < r.b;
        return k < r.k;
    }
};
 
map<edge, node*> mp;
map<pair<int, int>, int> lv;
map<int, int> vi[20][100009];
vector<pair<int, int> > v[20][100009];
int deg[20][100009];
 
void update(node* x)
{
    x->size = 1; x->mn = nullptr;
    if (x->f) x->mn = x;
    if (x->l) x->size += x->l->size;
    if (x->r) x->size += x->r->size;
 
    if (x->r && x->r->mn && !(x->f)) x->mn = x->r->mn;
    if (x->l && x->l->mn) x->mn = x->l->mn;
}
 
void rotate(node* x)
{
    if (!x->p) return;
    node* p = x->p, *b;
    if (p->l == x) {
        p->l = b = x->r;
        x->r = p;
    }
    else {
        p->r = b = x->l;
        x->l = p;
    }
    x->p = p->p;
    p->p = x;
    if (b) b->p = p;
    if (x->p) {
        if (x->p->l == p)
            x->p->l = x;
        else
            x->p->r = x;
    }
    update(p); update(x);
}
 
void splay(node* x)
{
    while (x->p) {
        node* p = x->p, *g = p->p;
        if (g) {
            if ((x == p->l) == (p == g->l)) rotate(p);
            else rotate(x);
        }
        rotate(x);
    }
}
 
void flagUp(int a, int b, int k, bool f) 
{
    node* x = mp[edge(a, b, k)];
    splay(x);
    x->f = f;
    update(x);
}
 
void addR(node* x, node* t) //Splay tree의 가장 오른쪽에 수 추가
{
    while (x->r) {
        x->size++;
        if (t->f && !x->mn)
            x->mn = t;
        x = x->r;
    }
    x->size++;
    if (t->f && !x->mn)
        x->mn = t;
    x->r = t;
    t->p = x;
    splay(t);
}
 
void join(node* a, node* b) //두 Splay tree를 연결
{
    while (a->r) a = a->r;
    splay(a);
    a->r = b; b->p = a;
    update(a);
}
 
int qry(int a, int b, int k) //레벨 k의 그래프에서 a, b의 연결성 판별
{
    if (mp.find(edge(a, a, k)) == mp.end() || mp.find(edge(b, b, k)) == mp.end()) return 0;
    node* na = mp[edge(a, a, k)], *nb = mp[edge(b, b, k)];
    splay(na);
    node* x = nb;
    while (x->p) x = x->p;
    splay(nb);
    if (x == na) return 1;
    else return 0;
}
 
void reroot(int a, int k) //레벨 k의 그래프에서 a를 Euler Tour의 루트로 만듦
{
    node* n = mp[edge(a, a, k)];
    splay(n);
    node* tl = n->l, *tr = n->r;
    if (!tl || !tr) return;
    n->l = nullptr; n->r = nullptr; n->mn = nullptr; n->size = 1;
    if (n->f) n->mn = n;
    tl->p = nullptr; tr->p = nullptr;
    join(tr, tl);
    addR(tl->p, n);
}
 
void conn(int a, int b, int k) // 레벨 k의 포레스트에 간선 (a, b) 추가
{                                    
    if (qry(a, b, k)) return;
    if (mp.find(edge(a, a, k)) == mp.end()) {
        node* t = new node();
        t->size = 1; t->a = a; t->b = a;
        mp[edge(a, a, k)] = t;
    }
    if (mp.find(edge(b, b, k)) == mp.end()) {
        node* t = new node();
        t->size = 1; t->a = b; t->b = b;
        mp[edge(b, b, k)] = t;
    }
    node* na = mp[edge(a, a, k)], *nb = mp[edge(b, b, k)];
    reroot(a, k); reroot(b, k);
    splay(na); splay(nb);
    node* x = new node(), *y = new node();
    x->size = y->size = 1;
    x->a = a; x->b = b;
    y->a = b; y->b = a;
    addR(na, x);
    join(x, nb);
    addR(x, y);
    mp[edge(a, b, k)] = x;
    mp[edge(b, a, k)] = y;
}
 
void connEdge(int a, int b, int k) //레벨 k의 그래프에서 간선 (a, b) 연결
{
    if (qry(a, b, k)) {
        v[k][a].push_back(make_pair(b, v[k][b].size()));
        v[k][b].push_back(make_pair(a, (int)v[k][a].size() - 1));
        vi[k][a][b] = (int)v[k][b].size() - 1;
        vi[k][b][a] = (int)v[k][a].size() - 1;
        deg[k][a]++; deg[k][b]++;
        if (deg[k][a] == 1) flagUp(a, a, k, true);
        if (deg[k][b] == 1) flagUp(b, b, k, true);
    }
    else {
        conn(a, b, k);
        flagUp(a, b, k, true);
        flagUp(b, a, k, true);
    }
    lv[make_pair(a, b)] = k; lv[make_pair(b, a)] = k;
}
 
void disconn(int a, int b, int k) //레벨 k의 포레스트에서 간선 (a, b) 제거
{
    if (mp.find(edge(a, b, k)) == mp.end()) return;
    node* x = mp[edge(a, b, k)], *y = mp[edge(b, a, k)];
    splay(x);
    node* tl = x->l, *tr = x->r;
    if (tl) tl->p = nullptr;
    if (tr) tr->p = nullptr;
    splay(y);
    bool f = (tl && (tl == y || tl->p));
    if (y->l) y->l->p = nullptr;
    if (y->r) y->r->p = nullptr;
    if (f) {
        if (y->l && tr)
            join(y->l, tr);
    }
    else {
        if (y->r && tl)
            join(tl, y->r);
    }
    x->l = x->r = x->p = x->mn = y->l = y->r = y->p = y->mn = nullptr;
    mp.erase(edge(a, b, k)); mp.erase(edge(b, a, k));
    delete x; delete y;
}
 
void disconn(int a, int b) //간선 (a, b) 제거
{
    if (lv.find(make_pair(a, b)) == lv.end()) return;
    int lp = lv[make_pair(a, b)];
    if (mp.find(edge(a, b, lp)) == mp.end()) { //포레스트에 포함되지 않은 간선일 경우
        v[lp][a][vi[lp][b][a]].first = 0; v[lp][b][vi[lp][a][b]].first = 0;
        deg[lp][a]--; deg[lp][b]--;
        if (!deg[lp][a]) flagUp(a, a, lp, false);
        if (!deg[lp][b]) flagUp(b, b, lp, false);
    }
    int rpa = 0, rpb = 0;
    for (int k = lp; k >= 0; k--) {
        disconn(a, b, k);
        if (qry(a, b, k)) continue;
        if (rpa) {
            conn(rpa, rpb, k);
            continue;
        }
        node* na = mp[edge(a, a, k)], *nb = mp[edge(b, b, k)];
        splay(na); splay(nb);
        if (na->size > nb->size)
            swap(na, nb);
        node* x = na->mn;
        while (x) { //작은 트리의 간선 레벨 증가
            int p = x->a, q = x->b;
            if (p > q) {
                connEdge(p, q, k + 1);
                flagUp(p, q, k, false);
                flagUp(q, p, k, false);
            }
            splay(x);
            if (!x->r) x = nullptr;
            else x = x->r->mn;
        }
        splay(na);
        x = na->mn;
        while (x && !rpa) { //대체 간선 탐색
            int n = x->a;
            while (!v[k][n].empty() && !rpa) {
                int tn = v[k][n].back().first;
                if (tn) {
                    if (qry(n, tn, k))
                        connEdge(n, tn, k + 1);
                    else { //대체 간선 발견
                        rpa = n; rpb = tn;
                        conn(n, tn, k);
                        flagUp(n, tn, k, true);
                        flagUp(tn, n, k, true);
                    }
                    v[k][tn][v[k][n].back().second].first = 0;
                    deg[k][n]--; deg[k][tn]--;
                    if (!deg[k][n]) flagUp(n, n, k, false);
                    if (!deg[k][tn]) flagUp(tn, tn, k, false);
                }
                v[k][n].pop_back();
            }
            splay(x);
            if (!x->r) x = nullptr;
            else x = x->r->mn;
        }
    }
    lv.erase(make_pair(a, b)); lv.erase(make_pair(b, a));
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 0; i < q; i++) {
        int t, a, b; cin >> t >> a >> b;
        if (t == 1) connEdge(a, b, 0);
        else if (t == 2) disconn(a, b);
        else cout << qry(a, b, 0) << '\n';
    }
    return 0;
}

 

 

출처, 참고 자료

• http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/17/Small17.pdf
• https://en.wikipedia.org/wiki/Dynamic_connectivity
• http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf
• 그래프 제작 : https://csacademy.com/app/graph_editor/