求强连通分量Tarjan算法
2024-08-26 13:33:53
int dfn[]; // 时间戳
int dfn_num = ; // 时间
int low[]; // 节点u所能访问到的最小时间戳 int inSt[]; // 节点u是否在栈中. int st[];
int top = ; // 我们维护的信息.
int col[]; // 给节点染色, 同一个连通块的节点应该是同一个颜色的.
int col_num = ; // 颜色值.
int size[]; // 每个颜色值所拥有的块数. /* 第一步: 访问当前节点的所有子节点: 子节点有三种
第一种: 未访问过的, 我们对它进行访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.
第二种: 访问过的,并且在栈中,我们直接更新我们 当前 节点的low[] --> 注意 应该用low[u] 和 dfn[v]比较.
第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染色了,属于一个连通块了.
第二步: 如果dfn[u] == low[u] 说明 已经找到一个连通块了.
这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.
*/ void Tarjan(int u) {
int v, i;
dfn[u] = low[u] = ++dfn_num; //添加时间戳.
st[++top] = u; // 进栈
inSt[u] = true; // 标示在栈
for (i=head[u]; i; i=edge[i].lst) {
v = edge[i].to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inSt[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
col_num++;
do {
inSt[st[top]] = false;
col[st[top]] = col_num;
size[col_num]++;
} while (st[top--] != u);
}
}
简单数据
/*
input:
6 8
1 3
3 5
5 6
4 6
4 1
1 2
2 4
3 4
out:
low : 1 1 3 1 6 4
col : 3 3 3 3 2 1
size: 1 1 4 0 0 0
*/
板子题: http://codevs.cn/problem/1332/
最新文章
- View的绘制、事件传递过程
- Android进程间通信之socket通信
- GZFramwork快速开发框架演练之会员系统(一)框架源码下载
- [maven] settings 文件节点配置详解
- VMware系统运维(三 )SQL Server 2008 R2安装
- MVC——数据库增删改查(Razor)
- Winedt 7.0 Build: 20120321 永久试用方法 WinEdt 7.0 破解
- 【HDOJ】1394 Minimum Inversion Number
- 无法更新 EntitySet“Ips_Articles”,因为它有一个 DefiningQuery,而 <;ModificationFunctionMapping>; 元素中没有支持当前操作的 <;InsertFunction>; 元素。
- 【转】四步完成win7 ubuntu双系统安装(硬盘,无需光驱)
- git从github下载代码
- Makefile分析基础
- IT只忍者龟Photoshop简单人像的头发抠图过程
- SQL点滴33—SQL中的字符串操作
- Linux ssh双向免密认证
- [HDU 3507]Print Article
- Codeforces Round #542 (Div. 1) 题解
- AD7729_双通道Sigma-Delta ADC
- SQLPLUS 命令
- nodejs之crypto加密算法