首页 > 代码库 > tarjan求强联通分量 模板

tarjan求强联通分量 模板

 1 void tarjan(int u) 2 { 3     dfn[u]=low[u]=++dfs_clock; 4     stack_push(u); 5      6     for (int c=head[u];c;c=nxt[c]) 7     { 8         int v=to[c]; 9         if (!dfn[v])10         {11             tarjan(v);12             low[u]=min(low[u],low[v]);13         }14         else if (!scc[v])15             low[u]=min(low[u],dfn[v]);16     }17     18     if (low[u]==dfn[u])19     {20         scc_cnt++;21         int cur;22         for (;;)23         {24             scc_size[scc_cnt]++;25             cur=stack_pop();26             scc[cur]=scc_cnt;27             if (cur==u)28                 break;29         }30     }31 }

 

tarjan求强联通分量 模板