`
lovnet
  • 浏览: 6670709 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

Tarjan算法求有向图强连通分量

 
阅读更多

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

    求有向图的强连通分量(scc)Tarjan算法.docx

    Tarjan 的强连通分量算法的Python实现

    )图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...

    tarjan算法

    Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...

    有向图的强连通分量

    详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。

    强连通分量(Strongly Connected Components)查找 原理熟悉,深度搜索,小白入手无压力

    强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组节点,这些节点之间互相可达。在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有...

    一个很好的强连通分量的课件

    而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...

    tarjan(e):Tarjan 的强连通分量算法-matlab开发

    实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...

    Tarjan算法模板

    C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。

    StronglyConnectedComponents:Tarjan算法的实现,以在有向图中找到强连通的分量

    C语言中的强连接组件Tarjan算法的实现,用于在有向图中找到强连接的组件。 图在graph.gx文件中表示。 节点数,每个节点的名称和每个节点的边缘应在不同的行中声明。 请以graph.gx为例。 我使用了伯克利大学开发的...

    C语言常见问题及算法专题整理资料

    约瑟夫环问题,魔方算法 迷宫探路 有向图强连通分量 线段树解在程序中的应用 Tarjan算法 Hash函数英语 RMQ算法

    算法模板1

    简介细节一道例题16 字符串使用手册18 日期处理模板19 最近公共祖先倍增查询20. 有向图强连通分量(Tarjan)21. 最长公共上升子序列问题描述问题分

    lyq-algorithms-lib:lyq算法库,涉及到相关数据挖掘,解压缩,模式匹配,图算法等多领域算法

    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....

    csci-163b

    有向图 深度优先搜索算法 连接的组件 深度优先树 前后号码 边缘类型(树,后退,前进,交叉) DAG拓扑排序(有向无环图) Kosaraju强连接组件算法 Tarjan Stronlgy连通组件算法 wgraph Kruskal最小生成树算法不相...

    kuangbin acm模板超级好用

    2.3 扩展欧几里得算法(求 ax+by=gcd 的解以及逆元) . . . . . . . . . . . . . . . 27 2.4 求逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 扩展欧几里德法 ...

Global site tag (gtag.js) - Google Analytics