有向图强连通分支

算法

在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。有向图G的极大强连通子图称为G的强连通分支。

Tarjan算法

dfn[i]表示编号为i的节点在DFS过程中的访问序列（也可以叫做开始时间）。在DFS过程中会形成一搜索树。在搜索树上越先遍历到的节点，dfn值越小

low[i]表示从i节点出发DFS过程中i下方结点（开始时间大于dfn[i]，且由i可达的节点）所能到达的最早的节点的开始时间，初始时dfn[i]=low[i]

void Tarjan(int u)
{dfn[u]=low[u]=++index;stack.push(u);for each(u,v) in E{if(v is not visted){tarjan(v);low[u]=min(low[u],low[v];)}else if(v in stack)low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){ //u是一个强连通分量的根 do{v=stack.popprint v标记v不在栈中}while(u!=v)//退栈，把整个强连通分量都弹出来 }
}//复杂度O(E+V) 

题目

CCF 201509-4 高速公路（100分）

HDU1269 迷宫城堡【有向图强连通分支】

HDU1827 Summer Holiday【有向图强连通分支+缩点】

HDU2767 Proving Equivalences【有向图强连通分支+缩点】

HDU3836 Equivalent Sets【有向图强连通分支+缩点】

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！