连通分量
连通分量编号递减的顺序一定是拓扑序
有向图——强连通分量
将有向图通过缩点的方法，转换成一个有向无环图(DAG)
缩点：将所有连通分量缩成一个点。
![ltfl]()
四条边
树枝边：DFS时经过的边，即DFS搜索树上的边
前向边：与DFS方向一致，从某个结点指向其某个子孙的边。
后向边：与DFS方向相反，从某个结点指向其某个祖先的边。（返祖边）
横叉边(x,y)：从某个结点指向搜索树中的另一子树中的某结点的边。
tarjan算法模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp; //等于时间戳
stk[ ++ top] = u; //将当前节点加入栈中
in_stk[u] = true; //记录当前节点是否在栈中
//遍历u所有能到的点
for (int i = h[u];~i;i = ne[i])
{
int j = e[i];
//如果当前这个点还没有被遍历过
if (!dfn[j])
{
tarjan(j);
//更新u能到的哪个点的最小值
low[u] = min(low[u],low[j]);
}
//如果这个点还在栈中
else if (in_stk[j])
low[u] = min(low[u],dfn[j]);
}
//如果遍历完后，发现u能到的最前面一个点就是自己
//则它就是这个强连通分量的最高点
if (dfn[u] == low[u])
{
int y;
//强连通分量个数加一
++ scc_cnt;
do
{
//取出栈顶元素
y = stk[top --];
//标记这个元素已经不在栈中
in_stk[y] = false;
//标记这个节点属于哪个强连通分量
id[y] = scc_cnt;
}while (y != u);//如果到了自己，则退出循环
}
}
|
无向图——双连通分量
![wxt]()
