【模板】Tarjan算法与有向图的强连通性
2024-08-26 10:57:54
概念
流图
给定一个有向图G= (V,E),若存在r∈V满足,满足从r出发能够到达V中所有的点,则称G是一个流图,记为(G,r),其中r是流图的源点。
流图的搜索树
在一个流图(G,r)上从r出发,进行深度优先遍历(DFS),每个点只访问一次。所有发生递归的变(u,v)(换言之,从x到y是对y的第一次访问)构成的一颗以r为根的树我们把它称为流图(G,r)的搜索树。
时间戳
同时,我们在深度优先遍历的过程中按照每个节点第一次被访问的时间顺序,依次给予流图中每个点1~n的标记,该点的标记被称作时间戳,用dfn[u]表示。
追溯值
设subtree(u)是以u为根的子树。u的追溯值low[u]我们这样定义满足以下条件中任意一个的点v的最小时间戳:
- 从u出发的边指向的点v在栈中。
- 在搜索树上以u为根的子树上的点v。
边的分类
对于流图中的有向边(u,v),必是以下四种边之一:
- 树枝边,指的是搜索树中的边,即u是y的父亲节点。
- 前向边,指的是搜索树中u是v的祖先节点。
- 后向边,指的是搜索树中v是u的祖先节点。
- 横叉边,指的是除了以上三种边之外的边,它一定满足dfn[v] <dfn[u]。
算法流程
- 当前节点u第一次被访问时,把u入栈,初始化low[u] = dfn[u].
- 扫描从u出发的每一条边(u,v)。
- 若v没被访问过,则说明(u,v)是树枝边,递归访问v,从y回溯之后,令low[u] = min(low[u], low[v])。
- 若v别访问过并且v在栈中,则令low[u] = min(low[x], dfn[v]);
- 从v回溯之前,判断是否有(low[u] == dfn[u])。若成立,则不断从栈中弹出节点,直至u出栈。
p.s.绿色的点是当前访问的点,黄色的点是已经访问结束的点,灰色的点是未访问完全(正在访问以它为根节点的子树);
p.s.p.s.黑色的序号代表节点的编号,蓝色的序号代表该点的dfn值,红色的序号代表该点的low值;
p.s.p.s.p.s.红色的边代表树枝边,深蓝色的边代表前向边,水蓝色的边代表后向边,橙色的边代表横叉边。
代码
#include<bits/stdc++.h>
using namespace std; const int MAXN = , MAXM = ; //加边
int Head[MAXN], Next[MAXM], To[MAXM], edgenum = ;
inline void Add_edge(int from, int to)
{
Next[++ edgenum] = Head[from], Head[from] = edgenum, To[edgenum] = to;
} //tarjan
int dfn[MAXN], ti = , sta[MAXN], top = , color[MAXN], cnt = , low[MAXN], num[MAXN], vis[MAXN];
inline void dfs(int u)
{
dfn[u] = low[u] = ++ ti, vis[u] = , sta[++ top] = u;
for(int i = Head[u]; i != -; i = Next[i])
{
int v = To[i];
if(!dfn[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else
if(vis[v]) low[u] = min(dfn[v], low[u]);
}
if(dfn[u] == low[u])
{
color[u] = ++cnt;
num[cnt] ++;
for(;sta[top] != u;)
{
color[sta[top]] = cnt;
vis[sta[top]] = ;
num[cnt] ++;
top --;
}
top --;
}
return;
}
inline int tarjan(int n)
{
int ans = ;
for(int u = ; u <= n; ++ u)
if(!color[u]) dfs(u);
for(int i = ; i <= cnt; ++ i)
if(num[i] > ) ans ++;
return ans;
} int main()
{
memset(Head, -, sizeof(Head));
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++ i)
{
int x, y;
scanf("%d%d", &x, &y);
Add_edge(x, y);
}
printf("%d\n", tarjan(n));
return ;
}
最新文章
- 不太被人提起的%%lockres%%的妙用
- AlertDialog对话框简单案例
- 轻松自动化---selenium-webdriver(python) (三)
- Eclipse统计代码行数
- js 定时函数
- 公司mysql数据库设计与优化培训ppt
- jq 换图片路径
- linux fork函数与vfork函数,exit,_exit区别
- Hamming code
- 给你的git仓库瘦身
- Ubuntu shortcuts
- JNI错误总结(转)
- vue-router2.x
- [翻译]成为顶尖程序员应当学什么?Python、C还是Ruby?
- 使用Spring实现读写分离( MySQL实现主从复制)
- js_7_dom文本
- Android程序员的Flutter学习笔记
- UOJ#172. 【WC2016】论战捆竹竿 字符串 KMP 动态规划 单调队列 背包
- 使用Selenium模块报错的解决办法 (FileNotFound,WebDriverException)
- snv的使用
热门文章
- Mongodb操作之查询(循序渐进对比SQL语句)(转http://www.tuicool.com/articles/UzQj6rF)
- C# 提高必备精品--你所需要的NET笔记
- java加载redis以及基本操作
- 后台数据校验-BeanCheck
- oracle数据库字符集和客户端字符集(2%)是不同的,字符集转化可能会造成不可预期的后果
- java队列queue的我觉得很好的使用方式
- gulp &; webpack整合
- 【javascript】javasrcipt设计模式之策略模式
- 横向开关(switch)
- 插入外置网卡端口顺序混乱--linux系统