博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
tarjan强连通算法
阅读量:4319 次
发布时间:2019-06-06

本文共 1258 字,大约阅读时间需要 4 分钟。

#include 
#include
using namespace std;const int MAX_N=100;const int MAX_M=10000;struct edge{ int v,next; int len;}E[MAX_M];int p[MAX_N],eid;void init(){ memset(p,-1,sizeof(p)); eid=0;}void insert(int u,int v){ E[eid].v=v; E[eid].next=p[u]; p[u]=eid++;}void tarjan(int u){ dfn[u]=low[u]=++idx; s[top++]=u; in_stack[u]=true; for(int i=p[u];i+1;i=E[i].next){ int v=E[i].v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(in_stack[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ ++scc; do{ belong[s[--top]]=scc; in_stack[s[top]]=false; }while(s[top]!=u); }}int main() { int n,m; init(); cin>>n>>m; for(int i=0;i
>u>>v; insert(u,v); } memset(dfn,0,sizeof(dfn)); idx=0; for(int i=1;i<=n;++i){ if(!dfn[i]){ tarjan(i); } } for(int i=1;i<=scc;i++){ cout<<"block "<
<<": "; for(int j=1;j<=n;j++){ if(belong[j]==i){ cout<
<<" "; } } cout<

 

转载于:https://www.cnblogs.com/asdic/p/9723216.html

你可能感兴趣的文章
逆向-攻防世界-re2-cpp-is-awesome
查看>>
Oracle分割字符串 REGEXP_SUBSTR用法
查看>>
O/R Mapping实际开发经验之谈(转)
查看>>
今天才知道原来我还没弄清楚js中全局变量和局部变量的定义...
查看>>
用户心理特征
查看>>
【z05】聪明的质检员
查看>>
【5001】n皇后问题
查看>>
【codeforces 796D】Police Stations
查看>>
数据库事务与锁详解
查看>>
linux 配置ssh免密码登录
查看>>
《重构》的读后感
查看>>
MySQL索引分析和优化
查看>>
DB2中通用的存储进程分页法度典范
查看>>
Fetchmail 6.3.8
查看>>
俄罗斯邮政将迁移到Linux 有关机构已末尾测试Linux
查看>>
SunOS 4上MySQL详尽事变
查看>>
python升级后pip 不可用 卸载pip
查看>>
推送kafka消息失败
查看>>
Nginx日志增长过快详细分析
查看>>
View Controller Programming Guid for iOS 笔记
查看>>