强连通分量+缩点+拓扑排序 模板
（强连通建立新图）（tarjan找强连通分量）
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> typedef long long ll; const constexpr int maxN = 1e6+3; typedef int int_vec[maxN]; struct dag_helper { int n,t; dag_helper(int _n=-1,int _t=0):n(_n),t(_t) {} bool operator<(const dag_helper& d) const { return t > d.t; } }; int V,E; int_vec head,to,next,dfn,low,belong,S,end; int edge_count,time,scc_count,scc_edge_count,top,time_2; dag_helper helper[maxN]; void init() { std::fill_n(head,maxN,-1); std::fill_n(to,maxN,-1); std::fill_n(next,maxN,-1); std::fill_n(dfn,maxN,0); std::fill_n(low,maxN,0); std::fill_n(belong,maxN,-1); std::fill_n(end,maxN,0); scc_edge_count = 0; edge_count = 0; time = 0; scc_count = 0; top = -1; time_2 = 0; } void add(int u,int v) { to[edge_count] = v; next[edge_count] = head[u]; head[u] = edge_count++; } void scc_add(int u,int v) { u += V; v += V; to[edge_count+scc_edge_count] = v; next[edge_count+scc_edge_count] = head[u]; head[edge_count+scc_edge_count] = edge_count+scc_edge_count; ++scc_edge_count; } void targan(int x) { if (dfn[x]) return; dfn[x] = low[x] = ++time; S[++top] = x; for (int i=head[x];i>=0;i=next[i]) { int y = to[i]; if (!dfn[y]) { targan(y); if (low[x] > low[y]) low[x] = low[y]; } else if ((belong[y] == -1) and (low[x] > dfn[y])) low[x] = dfn[y]; } if (dfn[x] == low[x]) { while (true) { belong[S[top]] = scc_count; if (S[top--] == x) break; } ++scc_count; } } void shrink() { for (int i=0;i<V;++i) for (int j=head[i];j>=0;j=next[j]) { int t = to[j]; if (belong[i] != belong[t]) scc_add(belong[i],belong[t]); } } void dfs(int x) { for (int i=head[x];i>=0;i=next[i]) { int y = to[i]; if (!end[y]) dfs(y); } end[x] = ++time_2; } void dag() { for (int i=0;i<scc_count;++i) dfs(V+i); for (int i=0;i<scc_count;++i) { helper[i].t = end[V+i]; helper[i].n = i; } std::sort(helper,helper+scc_count); } void doit() { for (int i=0;i<V;++i) targan(i); shrink(); dag(); } int main() { V = 8; init(); add(0,1); add(1,2); add(1,4); add(1,5); add(2,3); add(2,6); add(3,2); add(3,7); add(4,0); add(4,5); add(5,6); add(6,5); add(6,7); add(7,7); doit(); for (int i=0;i<V;++i) std::printf("%d\n",belong[i]); for (int i=0;i<scc_count;++i) std::printf("%d %d\n",helper[i].n,helper[i].t); std::printf("FIN\n"); }注：
1.S为stack，可以用std::stack替代
2.helper最后的排序即为对应强连通分量的拓扑序（注意编号）
3.每个节点i属于belong[i]分量
4.节点编号、边编号从0开始，强联通节点编号从V开始，强联通边编号从E开始（初始时E == edge_count）
