第一次写强连通tarjan同时也是自己在hdu100题的记录:在有向图中的强连通分量,核心是深搜,dfn[]数组记录搜索顺序,low[]数组所能返回的最小的点;
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string.h>
using namespace std;
vector<int>G[10003];
int dfn[10003],low[10003],ss[10003],top=1,mm=0,idx=0;
bool instack[10003];
void tarjan(int u)
{
vector<int>::iterator it=G[u].begin();
int t,v,minc=dfn[u]=low[u]=++idx;
instack[u]=true;
ss[++top]=u;
for(;it!=G[u].end();++it)
{
if(!dfn[*it])
{
tarjan(*it);
if(low[*it]<low[u])
low[u]=low[*it];
}
else if(instack[*it])
low[u]=min(low[u],dfn[*it]);
}
if(dfn[u]==low[u])
{
mm++;
do
{
v=ss[top--];
instack[v]=false;
}while(u!=v);
}
if(mm>1)
return;
}
int main()
{
int x,y,n,m;
while(~scanf("%d%d",&n,&m)&&n+m)
{ memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(instack,false,sizeof(instack));
idx=mm=0;
top=1;
for(int i=0;i<10003;i++)
G[i].clear();
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
for(int i=1;i<=n&&mm<2;i++)
if(!dfn[i])
tarjan(i);
if(mm==1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
分享到:
相关推荐
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
求有向图的强连通分量(scc)Tarjan算法.docx
使用Tarjan算法进行快速计算强连通分量,C++语言实现。
Tarjan求有向图的强连通分量, */ #include #include #include #include #include using namespace std; const int MAXN = 1e5 + 10; struct Edge{ int to, next, dis; }edge[MAXN << 1];
纯代码
tarjan算法呕心沥血之作,动画演示,步步清晰可见,详细的描述了tarjan算法的工作过程,比网上的单纯的图片更加容易理解。
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
图论- 图的连通性- Tarjan 求强连通分量.rar
以下是使用C语言实现查找强连通分量的示例代码,基于深度优先搜索(DFS)算法和Tarjan算法: 在上面的示例中,我们使用邻接矩阵来表示有向图。tarjan()函数是整个算法的入口,它会遍历所有节点并调用findSCCs()函数...
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
Tarjan 算法是图论中非常实用 / 常用的算法之一,能解决强连通分量,双连通分量,割点和桥,求最近公共祖先(LCA)等问题。 关于 Tarjan 算法,笔者将用一系列文章系统介绍 Tarjan 算法的原理以及其主要解决的问题...
Tarjan 算法论文 DEPTH-FIRST SEARCH AND LINEAR GRAPH ALGORITHMS.pdf
更精细的追踪每一个步骤,力求完全剖析算法。
Tarjan算法的图文讲解,非常详细易懂。 强连通分量算法
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...