http://www.byvoid.com/blog/scc-tarjan/zh-hans/#comment-24176
http://blog.csdn.net/shiqi_614/article/details/7833628
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define FileIn freopen("in.ads","r",stdin)
#define FileOut freopen("out.ads","w",stdout)
#define N 155
#define M 22555
struct Vertex
{
int head;
}V[N];
struct Edge
{
int v,next;
}E[M];
int etop,top,index,dfn[N],low[N],S[N];
bool in[N];
void Init()
{
etop = top = index = 0;
memset(V,-1,sizeof(V));
memset(dfn,0,sizeof(dfn));
memset(in,false,sizeof(in));
}
void Add_Edge(int u,int v)
{
E[etop].v = v;
E[etop].next = V[u].head;
V[u].head = etop++;
}
void Tarjan(int u)
{
int v;
dfn[u] = low[u] = ++index;
in[u] = true;
S[++top] = u;
for(int i=V[u].head;i!=-1;i=E[i].next)
{
v = E[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else
if(in[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u])
{
puts("QiangLianTong:");
do
{
v = S[top--];
in[v] = false;
printf("%d ",v);
}while(u != v);
puts("\n***********\n");
}
}
int main()
{
FileIn;
int n,m,u,v;
while(~scanf("%d%d",&n,&m))
{
Init();
while(m--)
{
scanf("%d%d",&u,&v);
Add_Edge(u,v);
}
Tarjan(1);
}
return 0;
}
分享到:
相关推荐
求有向图的强连通分量(scc)Tarjan算法.docx
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组节点,这些节点之间互相可达。在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有...
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
C语言中的强连接组件Tarjan算法的实现,用于在有向图中找到强连接的组件。 图在graph.gx文件中表示。 节点数,每个节点的名称和每个节点的边缘应在不同的行中声明。 请以graph.gx为例。 我使用了伯克利大学开发的...
约瑟夫环问题,魔方算法 迷宫探路 有向图强连通分量 线段树解在程序中的应用 Tarjan算法 Hash函数英语 RMQ算法
简介细节一道例题16 字符串使用手册18 日期处理模板19 最近公共祖先倍增查询20. 有向图强连通分量(Tarjan)21. 最长公共上升子序列问题描述问题分
lyq-algorithms-liblyq算法库,涉及到相关数据挖掘,解压缩,模式匹配,图算法等多领域算法BloomFilter布隆过滤器算法。可以用来判读一个集合是否存在的问题原理是...Tarjan有向图强连通分量算法。Trie字典查找树算法
| TARJAN 强连通分量 7 | 弦图判断 7 | 弦图的 PERFECT ELIMINATION 点排列 7 | 稳定婚姻问题 O(N^2) 7 | 拓扑排序 8 | 无向图连通分支(DFS/BFS 邻接阵) 8 | 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) 8 | 有...
Algorithms 本次README修订为算法仓库Algorithms的第100次commit,首先我们...使用Tarjan算法求解强连通分量 Tarjan(Strongly-Connected-Components) 数组版的字典树 Trie(Array) 指针版的字典树 Trie(Pointer)
当前已支持算法:快速排序、插入排序、堆排序、归并排序、取最大、取最小、向下...包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断)
包含算法:dijkstra、floyd、SPFA、kruskal、prim、tarjan强连通分量、遍历、求哈密顿环、匈牙利算法求二分图最大匹配、连通性判断) 另外给喜爱算法的人推荐一本书:刘汝佳的《算法竞赛入门经典》,pan.baidu....
有向图 深度优先搜索算法 连接的组件 深度优先树 前后号码 边缘类型(树,后退,前进,交叉) DAG拓扑排序(有向无环图) Kosaraju强连接组件算法 Tarjan Stronlgy连通组件算法 wgraph Kruskal最小生成树算法不相...
2.3 扩展欧几里得算法(求 ax+by=gcd 的解以及逆元) . . . . . . . . . . . . . . . 27 2.4 求逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 扩展欧几里德法 ...