void tarjan(int u)
{
dfn[u]=low[u]=++dfs_clock;
stack_push(u); for (int c=head[u];c;c=nxt[c])
{
int v=to[c];
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (!scc[v])
low[u]=min(low[u],dfn[v]);
} if (low[u]==dfn[u])
{
scc_cnt++;
int cur;
for (;;)
{
scc_size[scc_cnt]++;
cur=stack_pop();
scc[cur]=scc_cnt;
if (cur==u)
break;
}
}
}
相关文章
- 强连通分量 ( Tarjan,邻接链表 )——The Bottom of a Graph ( POJ 2553 )
- 图论——强连通分量:Tarjan算法。
- 图论算法(6) --- Tarjan算法求强连通分量
- 图论——强连通分量:Tarjan算法——练习1
- POJ 1904 King's Quest 强联通分量+输入输出外挂
- hdu 1213 求连通分量(并查集模板题)
- 图论算法-Tarjan模板 【缩点;割顶;双连通分量】
- poj1523求割点以及割后连通分量数tarjan算法应用
- tarjan算法求桥双连通分量 POJ 3177 Redundant Paths
- 【题解】NOIP 2015 信息传递(tarjan 强连通分量)