しかも，DFS1回だけ実行．

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

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

```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);
}
```