Finding Dominators in Directed Graphs (SEMI-NCA Algorithm)

概要

\(r\) を始点とする有向グラフ \(G = (V, A, r)\) において、各頂点 \(v\) を直近で支配する頂点 (an immediate dominator) を求める。

SEMI-NCA では、各頂点 \(v\) の semidominator \(sdom(v)\) を求め、この semidominator を元に徐々に dominator tree を構築する。

各頂点 \(w\) の親頂点 \(parent(w)\) から dominator tree を遡り、 \(x \le sdom(w)\) を満たす初めの頂点 \(x\) を immediate dominator とする。

dominator tree の構築での最悪計算量は \(O(|V|^2)\) になるが、実用的なケースでは高速に動作することが期待できる。
(競プロ的には、時間がかかるケースが人為的に生成される可能性がある)

計算量

\(N = |V|\), \(M = |A|\) とする

Lengauer-Tarjan Algorithm の simple version の LINK-EVAL を用いて semidominator を構築する場合は \(O(N^2 + M \log N)\)

実装

#include<vector>
using namespace std;

#define N 100003

int n;
vector<int> g[N];

vector<int> vs;
int order[N];
int prt[N];
int doms[N], semi[N];
int anc[N], label[N];
vector<int> rg[N];

inline void link(int v, int w) {
  anc[w] = v;
}

int compress(int v, int w) {
  if(w == anc[w]) {
    return w;
  }

  anc[v] = compress(w, anc[w]);
  if(label[w] < label[v]) {
    label[v] = label[w];
  }
  return anc[v];
}

inline int eval(int v) {
  if(v == anc[v]) {
    return label[v];
  }

  compress(v, anc[v]);
  return label[v];
}

void dfs(int v) {
  order[v] = vs.size();
  vs.push_back(v);
  for(int w : g[v]) {
    if(order[w] != -1) continue;
    prt[w] = v;
    dfs(w);
  }
}

void dominator(int s) {
  for(int i=0; i<n; ++i) order[i] = -1, prt[i] = -1;
  vs.reserve(n);

  dfs(s);

  for(int i=0; i<n; ++i) semi[i] = label[i] = order[i], doms[i] = -1;
  for(int i=0; i<n; ++i) anc[i] = i;

  for(int v=0; v<n; ++v) {
    for(int w : g[v]) {
      rg[w].push_back(v);
    }
  }

  for(int i=n-1; i>0; --i) {
    int w = vs[i];
    for(int v : rg[w]) {
      int s_min = eval(v);
      if(s_min < semi[w]) semi[w] = s_min;
    }
    label[w] = semi[w];
    link(prt[w], w);
  }

  doms[s] = s;
  for(int i=1; i<n; ++i) {
    int w = vs[i];
    int x = prt[w];
    while(semi[w] < order[x]) x = doms[x];
    doms[w] = x;
  }
}

Verified

  • AOJ: "0294: Catch a Thief": source (C++11, 0.17sec)

参考

  • Georgiadis, Loukas, Robert E. Tarjan, and Renato F. Werneck. "Finding dominators in practice." Journal of Graph Algorithms and Applications 10.1 (2006): 69-94.

戻る