tarjan

缺乏、安全感 2021-11-22 08:48 294阅读 0赞

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<ctime>
    using namespace std;
    const int N=50005;
    int n,m,head[N],dfs[N],stack[N],low[N],cnt,t,top,ans;
    bool vis[N];
    struct node{
        int u,v,next;
    }edge[N];
    void push(int u,int v){
        ++cnt;
        edge[cnt].u=u;
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    void tarjan(int u){
        dfs[u]=low[u]=++t;
        stack[++top]=u;
        vis[stack[top]]=1;
        for(int i=head[u];i!=-1;i=edge[i].next){
            if(!dfs[edge[i].v]){
                tarjan(edge[i].v);
            }
            if(vis[edge[i].v]){
                low[u]=min(low[u],low[edge[i].v]);
            }
        }
        if(low[u]==dfs[u]){
            for(++ans;stack[top+1]!=u;){
                vis[stack[top--]]=0;
            }
        }
    }
    int main(){
        int u,v;
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&u,&v);
            push(u,v);
        }
        for(int i=1;i<=n;i++){
            if(!dfs[i]){
                tarjan(i);
            }
        }
        printf("%d\n",ans);
        system("pause");
        return 0;
    }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11194246.html

发表评论取消回复

表情：

评论列表（有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

相关 Tarjan算法

目录 Tarjan算法预备知识算法思路代码 Tarjan算法预备知识有向图：由有向边的构成的

ゝ一世哀愁。/ 2023年06月01日 06:11/ 0 赞/ 8 阅读

相关 Tarjan 算法

Tarjan 算法一.算法简介 Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。我们定义：如果

一时失言乱红尘/ 2023年01月16日 06:21/ 0 赞/ 128 阅读

相关 Tarjan算法 POJ2186

题目链接 [点击这里][Link 1] Tarjan算法适用情形有向图，求强连通分量。此题中，以Tarjan算法为基础，求解并标记了相应的连通分量，

ゝ一纸荒年。/ 2022年11月27日 11:30/ 0 赞/ 180 阅读

相关 Tarjan算法

下面详细介绍一下Tarjan算法的基本思路：　　　　　　1.任选一个点为根节点，从根节点开始。　　　　　　2.遍历该点u所有子节点v，并标记这些子节点v已被访问

超、凢脫俗/ 2022年06月08日 06:30/ 0 赞/ 262 阅读

相关 tarjan算法转载

转载博主:[点击打开链接][Link 1] 讲的非常好，肯定可以看懂。 tarjan算法，一个关于图的联通性的神奇算法。基于DFS（迪法师）算法，深度优先搜索一张有向图。

蔚落/ 2022年05月26日 01:00/ 0 赞/ 223 阅读

相关 tarjan算法讲解

时隔好久回来复习tarjan算法，又看了许多网上的文章，在此再给一篇觉得不错的文章：[mengxiang000][] 全网最详细tarjan算法讲解，我不敢说别的。反正其他t

ゝ一世哀愁。/ 2022年04月13日 06:12/ 0 赞/ 315 阅读

相关 tarjan

include<iostream> include<cstdio> include<cstdlib> include<cmath> in

缺乏、安全感/ 2021年11月22日 08:48/ 0 赞/ 295 阅读

相关 Tarjan进阶

BLO 关键字：tarjan 树上dp 原图有环，然可利用tarjan深度优先搜索树，假设去掉的点是u，考虑三个方向的转移 1. 本身：2\(n-1)，与除本身外任

╰半夏微凉°/ 2021年11月16日 10:14/ 0 赞/ 317 阅读

相关 tarjan算法习题

dfs树与tarjan算法标签（空格分隔）： 517coding problem solution dfs树 tarjan --------------------

水深无声/ 2021年10月31日 16:42/ 0 赞/ 343 阅读

相关 tarjan学习笔记

1.$tarjan$求强连通分量思想：在$dfs$的过程中，把强连通分量中的点入栈，当找到一个强连通分量的最起始的点，就将其所在强连通分量中的点出栈。缩点把强连通分

小咪咪/ 2021年10月30日 05:56/ 0 赞/ 289 阅读