深さ優先探索1回で強連結成分分解 C++

前回の続き．

今回は強連結成分分解する．

しかも，DFS1回だけ実行．

アルゴリズムは非常にシンプル．そして，結構分かりやすいと思うのだが．

アルゴリズムの解説等は以下が比較的分かりやすいと思う．

http://www.ics.uci.edu/~eppstein/161/960220.html#sca

void visit(const Graph &g, int *label, stack<Vertex> &s, const Vertex &u,
           int *num, int *low, int &index);

void scc(const Graph &g, int *label) {  //  label[a] == label[b] ⇔ aとbは同じ連結成分
  const int n = g.succ.size();
  int index = 0, *num = new int[n], *low = new int[n];
  fill_n(label, n, -1);
  stack<Vertex> s;
  for (Vertex i = 0; i < n; ++i)
    if (label[i] == -1) visit(g, label, s, i, num, low, index);
}

void visit(const Graph &g, int *label, stack<Vertex> &s,const Vertex &u,
           int *num, int *low, int &index) {
  s.push(u);
  low[u] = num[u] = ++index;
  foreach(Vertex v, g.succ[u]) {
    if (label[v] != -1) continue;
    if (num[v] == 0) visit(g, label, s, v, num, low, index);
    low[u] = min(low[u], low[v]);
  }
  if (num[u] == low[u]) {
    Vertex v;
    do v = s.top(), s.pop(), label[v] = u;
    while (v != u);
    label[u] = u;
  }
}

↑現実

↓理想（関数内関数が使えれば…）

void scc(const Graph &g, int *label) {
  const int n = g.succ.size();
  int index = 0, *num = new int[n], *low = new int[n];
  fill_n(label, n, -1);
  stack<Vertex> s;
  void visit(const Vertex &u) {
    s.push(u);
    low[u] = num[u] = ++index;
    foreach(Vertex v, g.succ[u]) {
      if (label[v] != -1) continue;
      if (num[v] == 0) visit(v);
      low[u] = min(low[u], low[v]);
    }
    if (num[u] == low[u]) {
      Vertex v;
      do v = s.top(), s.pop(), label[v] = u;
      while (v != u);
      label[u] = u;
    }
  }
  for (Vertex i = 0; i < n; ++i) if (label[i] == -1) visit(i);
}

関数内関数を許可すると再帰とか，相互呼び出しとかで大変なのでしょうか．