#include<cstdio> #include<cstring> #include<vector> #include<stack> #define maxn 500//图的规模 using namespace std; vector<int> G[maxn];//邻接表存图 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt; stack<int> S; void dfs(int u){ pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i=0; i < G[u].size(); i++){ int v = G[u][i]; if(!pre[v]){ dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); }else if(!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]) { scc_cnt ++ ; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } } } void find_scc(int n){ dfs_clock = scc_cnt = 0; memset(sccno, 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i = 0; i < n; i++) if(!pre[i]) dfs(i); } int main() { int T,i; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); G[a].push_back(b); } find_scc(n); for(i=0;i<n;i++) { printf("%d ",sccno[i]); } printf("\n"); } return 0; }
图用 邻接表存储
sccno[i]表示 i所在的连通分量数
scc_cnt 表示一共的连通分量数
相关推荐
Tarjan 的算法将一个有向(可能是循环的!)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不...
求有向图的强连通分量(scc)Tarjan算法.docx
Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法,以及求最近公共祖先的离线Tarjan算法 (本篇文章...
C++实现Tarjan算法的一个简单模板,求有向图的强连通分量。时间复杂度为O(N+M)。
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组节点,这些节点之间互相可达。在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有...
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
C语言中的强连接组件Tarjan算法的实现,用于在有向图中找到强连接的组件。 图在graph.gx文件中表示。 节点数,每个节点的名称和每个节点的边缘应在不同的行中声明。 请以graph.gx为例。 我使用了伯克利大学开发的...
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
约瑟夫环问题,魔方算法 迷宫探路 有向图强连通分量 线段树解在程序中的应用 Tarjan算法 Hash函数英语 RMQ算法
简介细节一道例题16 字符串使用手册18 日期处理模板19 最近公共祖先倍增查询20. 有向图强连通分量(Tarjan)21. 最长公共上升子序列问题描述问题分
2.3 扩展欧几里得算法(求 ax+by=gcd 的解以及逆元) . . . . . . . . . . . . . . . 27 2.4 求逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 扩展欧几里德法 ...
| 无向图连通度(割) 3 | 最大团问题 DP + DFS 3 | 欧拉路径 O(E) 3 | DIJKSTRA 数组实现 O(N^2) 3 | DIJKSTRA O(E * LOG E) 4 | BELLMANFORD 单源最短路 O(VE) 4 | SPFA(SHORTEST PATH FASTER ALGORITHM) 4 ...
lyq-algorithms-liblyq算法库,涉及到相关数据挖掘,解压缩,模式匹配,图算法等多领域算法BloomFilter布隆过滤器算法。可以用来判读一个集合是否存在的问题原理是...Tarjan有向图强连通分量算法。Trie字典查找树算法
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最小生成树算法不相...