Dominator Tree on DAG

문제 상황은 다음과 같다 :

 

1) DAG에서 어떤 source vertex s가 주어진다.

2) 특정 간선 (혹은 정점) 하나를 삭제했을 때 도달 가능한 정점의 개수를 모든 간선(혹은 정점)에 대해 구하시오.

 

Naive한 방법은 직접 그래프에서 해당 간선 혹은 정점을 삭제한 후 그래프탐색을 통해 O(VE)정도 시간에 해결하는 것인데, 이를 O((N+M)lgN)정도 시간복잡도에 해결할 수 있게 해주는 것이 바로 Dominator Tree이다.

 

일단, source vertex에서 시작하는 그래프탐색을 통해, 삭제가 없어도 도달이 불가능한 정점들을 전부 삭제시켜두고 시작하자. 이제부터 언급할 정점들은 모두 s에서 어떤 경로를 통해 접근이 가능하다.

 

몇가지 정의를 짚고 넘어가자.

 

1) Dominator

어떤 정점 v(v≠s)에 대해, s에서 v로 오는 모든 경로들이 항상 통과하는 정점들의 집합을 Dom(v)라고 표기한다. 이때 자기 자신은 Dom(v)에 포함을 시키지 않는다.

 

2) Immediate Dominator

어떤 정점 v(v≠s)에 대해 Dom(v) 중 v와 가장 가까운 정점 u가 있을 것이다. (항상 s∈Dom(v)이므로 이러한 정점 u는 항상 존재한다) 이때 u=Idom(v)라 표기한다.

 

DAG에서의 Dominator Tree는 v(v≠s)와 Idom(v)를 간선으로 이은 형태이다. 만약 이 Dominator Tree를 만들었다면, 단순히 그 Tree위에서 DFS를 도는 식으로 위에 제시한 문제를 풀 수 있다.

 

이제 Dominator Tree를 구축하는 방법을 알아보도록 하자.

 

위상정렬 순으로 귀납적인 상황을 가정하자. 지금 추가할 정점 v이전에 등장하는 모든 정점들에 대한 Dominator Tree를 구축한 상황이다.

 

u->v로 직접적인 간선이 존재하는 u들의 집합을 In(v)라 명명하자. Idom(v)=LCA({ s | u∈In(v), s=Idom(u) })이다.

여기서 LCA는 Dominator Tree위에서 정의된다. 이제 문제는 다음과 같이 변형된다.

 

-트리가 주어지고, 리프 정점으로 정점이 추가되는 업데이트가 있을 때 LCA쿼리를 빠르게 지원하라.

 

일반적으로 LCA는 sparse table을 이용해 구하는데, 잘 생각해보면 리프 정점에 추가될때마다 해당되는 O(lgV)개의 table만 업데이트 해주면 끝나게 된다.

 

저런 방법으로 차례차례 Dominator Tree를 만들면 최종 시간복잡도 O((V+E)lgV)에 답을 찾을 수 있다.

 

또, 일반적인 Directed Graph에서도 Dominator Tree를 비슷한 시간복잡도에 구할 수 있다는데, 이것은 OI의 범위를 넘어섰다고 판단되어 나중에 ICPC에 나갈때나 다시 공부해보는 것으로 하겠다.(^^)

 

연습문제는 다음과 같다.

www.acmicpc.net/problem/19335-Dijkstra를 이용해 생성한 DAG위에서의 Dominator Tree

 

정답 코드입니다.

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, m;
pair<pii, LL> edg[200010];

LL d[200010];
vector<pil> link[200010];
priority_queue<pli, vector<pli>, greater<pli> > pq;
void dijkstra(){
    for(int i=1; i<=n; i++)d[i]=LLINF;
    pq.push(mp(0ll, 1));
    while(pq.size()){
        LL nc=pq.top().F;
        int nw=pq.top().S;
        pq.pop();
        if(d[nw]<=nc)continue;
        d[nw]=nc;
        for(auto i:link[nw])pq.push(mp(nc+i.S, i.F));
    }
}

vector<int> dag[200010], dom[200010];
int sp[200010][25], dep[200010], deg[200010], idom[200010];
int que[200010], fr, re;
int lca(int x, int y){
    if(dep[x]>dep[y])swap(x, y);
    for(int i=20; i>=0; i--){
        if(dep[y]-dep[x]>=(1<<i))y=sp[y][i];
    }
    if(x==y)return x;
    for(int i=20; i>=0; i--){
        if(sp[x][i]!=sp[y][i]){
            x=sp[x][i];
            y=sp[y][i];
        }
    }
    return sp[x][0];
}

void get_dominator_tree(){
    for(int i=1; i<=n; i++){
        for(auto j:dag[i])deg[j]++;
        idom[i]=i;
    }
    que[++re]=1;
    for(fr=1; fr<=re; fr++){
        for(auto i:dag[que[fr]]){
            if(idom[i]==i)idom[i]=que[fr];
            else idom[i]=lca(idom[i], que[fr]);
            deg[i]--;
            if(!deg[i]){
                que[++re]=i;
                dep[i]=dep[idom[i]]+1;
                sp[i][0]=idom[i];
                dom[idom[i]].eb(i);
                for(int j=1; j<=20; j++)sp[i][j]=sp[sp[i][j-1]][j-1];
            }
        }
    }
}

int sz[200010];
map<pii, LL> ans;
void dfs(int num, int par){
    sz[num]=1;
    for(auto i:dom[num]){
        dfs(i, num);
        sz[num]+=sz[i];
    }
    ans[mp(par, num)]=sz[num];
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %lld", &edg[i].F.F, &edg[i].F.S, &edg[i].S);
        link[edg[i].F.F].eb(edg[i].F.S, edg[i].S);
        link[edg[i].F.S].eb(edg[i].F.F, edg[i].S);
    }
    dijkstra();
    for(int i=1; i<=m; i++){
        if(d[edg[i].F.F]>d[edg[i].F.S])swap(edg[i].F.F, edg[i].F.S);
        if(d[edg[i].F.F]+edg[i].S==d[edg[i].F.S])dag[edg[i].F.F].eb(edg[i].F.S);
    }
    get_dominator_tree();
    dfs(1, 0);
    for(int i=1; i<=m; i++)printf("%d\n", ans[mp(edg[i].F.F, edg[i].F.S)]);
}