tarjan_scc_algo_v2.cpp

// 这种写法内存消耗大约是上一种写法的两倍，时间消耗二者差不多。
template <typename Arc>
struct SCC {
    int n;
    using Graph = vector<vector<Arc>>;
    Graph &g;
    function<int&(Arc &)> get_v;
    vector<int> scc_id;
    int scc_cnt;
    Graph scc_g; // 缩点建图

    SCC(int n, Graph &g,
        function<int&(Arc &e)> get_v = [](Arc &e) { return e; })
            : n(n),
              g(g),
              get_v(move(get_v)),
              scc_id(n + 1, -1),
              scc_cnt(0) {}  // SCCs are indexed from 0
    void dfs(int u) {
        static Graph inter_scc_arcs(n + 1);
        static vector<int> low(n + 1), order(n + 1);
        static vector<bool> in_stack(n + 1);
        static stack<int> s;
        static int time;
        order[u] = low[u] = ++time;
        s.push(u);
        in_stack[u] = true;

        for (auto &e : g[u]) {
            int& v = get_v(e);
            if (!order[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = min(low[u], order[v]);
            }
            if (!in_stack[v]) {
                inter_scc_arcs[u].push_back(e);
                get_v(inter_scc_arcs[u].back()) = scc_id[v];
            }
        }

        if (order[u] == low[u]) {
            scc_g.push_back({});
            while (true) {
                int v = s.top();
                s.pop();
                in_stack[v] = false;
                scc_id[v] = scc_cnt;
                scc_g.back().insert(scc_g.back().end(), inter_scc_arcs[v].begin(), inter_scc_arcs[v].end());
                if (u == v) break;
            }
            ++scc_cnt;
        }
    }

    int find_scc() {
        for (int i = 1; i <= n; i++) {
            if (scc_id[i] == -1) {
                dfs(i);
            }
        }
        return scc_cnt;
    }

    int find_scc_from(int start) {
        dfs(start);
        return scc_cnt;
    }
};

模板-强连通分量.cpp

template <typename Arc>
struct SCC {
    int n;
    using Graph = vector<vector<Arc>>;
    const Graph &g;
    function<int(const Arc &)> get_v;
    vector<int> low, order, scc_id;
    vector<bool> in_stack;
    int time, scc_cnt;
    stack<int> s;

    SCC(int n, const Graph &g, function<int(const Arc &e)> get_v = [](const Arc &e) { return e; }) :
            n(n), g(g), get_v(move(get_v)), low(n + 1), order(n + 1), scc_id(n + 1, -1), in_stack(n + 1), time(0),
            scc_cnt(0) {} // SCCs are indexed from 0
    void dfs(int u) {
        order[u] = low[u] = ++time;
        s.push(u);
        in_stack[u] = true;

        for (auto &e : g[u]) {
            int v = get_v(e);
            if (!order[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = min(low[u], order[v]);
            }
        }

        if (order[u] == low[u]) {
            while (true) {
                int v = s.top();
                s.pop();
                in_stack[v] = false;
                scc_id[v] = scc_cnt;
                if (u == v) break;
            }
            ++scc_cnt;
        }
    }

    int find_scc() {
        for (int i = 1; i <= n; i++) {
            if (!order[i]) {
                dfs(i);
            }
        }
        return scc_cnt;
    }

    int find_scc_from(int start) {
        dfs(start);
        return scc_cnt;
    }
};

Tarjan 的强连通分量算法求出的强连通分量恰好是按照它们的拓扑序倒着编号的。有时候不但要求出强连通分量还需要知道这些强连通分量的拓扑序，此时不必再对强连通分量进行拓扑排序，将它们按编号从大到小排列就是拓扑序。

强连通分量之间的有向边也可以在 DFS 的过程分辨出来。

for (auto &e : g[u]) {
  int v = get_v(e);
  if (!order[v]) {
    dfs(v);
    low[u] = min(low[u], low[v]);
  } else if (in_stack[v]) {
    low[u] = min(low[u], order[v]);
  }
  if (!in_stack[v]) {
    // u-->v 是强连通分量之间的边
  }
}

或者写成

for (auto &e : g[u]) {
  int v = get_v(e);
  if (!order[v]) {
    dfs(v);
    low[u] = min(low[u], low[v]);
    if (!in_stack[v]) {
      // u-->v 是强连通分量之间的边
    }
  } else if (in_stack[v]) {
    low[u] = min(low[u], order[v]);
  } else {
    // u-->v 是强连通分量之间的边
  }
}

如果是求固定起点的强连通分量，那么缩点建图可以这样写：

vector<vector<pair<int,int>> g(n + 1);
SCC<pair<int,int>> t(n, g, [](const auto& e) {return e.first;});
int scc_cnt = t.find_scc_from(1);
vector<vector<Edge>> scc_g(scc_cnt);
for (int i = 1; i <= n; ++i) {
    int x = t.scc_id[i];
    if (x >= 0) {
        for (const auto& e : g[i]) {
            int y = t.scc_id[e.first];
            if (x == y) {
              // do sth as you please
            } else {
                scc_g[x].emplace_back(y, e.second);
            }
        }
    }
}