有向图-强连通分量

在有向图 $G$ 中，如果两个顶点 $u,v$ 间有一条从 $u$ 到 $v$ 的有向路径，同时还有一条从 $v$ 到 $u$ 的有向路径，则称两个顶点强连通（strongly connected）。

如果有向图 $G$ 的任意两个顶点都强连通，称 $G$ 是一个强连通图。

有向非强连通图的极大强连通子图，称为强连通分量$SCC (strongly \ connected \ components)$ 。

如上图，强连通分量有：

1 3 4 2
5
6

对于有向图搜索树(dfs tree)有四种不同类型的边：树边（tree edge）、 返祖边（back edge）、前向边（forward edge）、横叉边（cross edge）。以下图为例，$4$ 种边含义如下：

如果白色的点代表未访问，灰色的点表示未处理完（子孙未访问结束），黑色表示全部访问结束。树边表示 dfs tree 实际访问的边，从灰色点访问白色的点。返祖边表示从当前点指向本节点祖先节点，从灰色的点访问灰色的点。有向图还存在前向边和横叉边，而无向图不存在这两种边。

• 1.树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。（灰->白）

• 2.返祖边（back edge）：示意图中以红色边表示（即 7->1 ），也被叫做回边，即指向祖先结点的边。（灰->灰）

• 3.前向边（forward edge）：示意图中以绿色边表示（即 3->6 ），它是在搜索的时候遇到子树中的结点的时候形成的。（灰->黑）

• 4.横叉边（cross edge）：示意图中以蓝色边表示（即 9->7），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点并不是当前结点的祖先。（灰->黑）

返祖边、前向边、横叉边都属于非树边，辅助理解强连通分量求解。

通过返祖边可能返回到更早的祖先，但是否是最早的祖先，要借助另外一个重要信息“最早时间戳” - low.

最早时间戳- low

在 dfs tree 中每个节点第一次访问的时间序号，成为“时间戳”，记为 dfn[x]

在搜索子树中，$x$ 通过自己或者 $x$ 子孙能够追溯到的祖先的最早（最小）的 $dfn$ 值就是“最早时间戳” ，记为 low[x] , 初始化为 low[x]=dfn[x].

请用下图，求出每个点的 dfn 和 low ，考虑如何与强连通分量之间的关系。

Tarjan求强连通分量

访问的时候，将所有新访问的节点入栈。利用 dfs 可以求解每个节点的 dfn 和 low , 当一个节点的 dfn 与 low 相等时，说明这个节点无法追溯到更早的祖先，那么栈顶到这个点所有的点都属于同一个强连通分量。

过程如下：

• 1. 当节点 $x$ 第一次被访问时，把 $x$ 入栈，标记 $x$ 的状态为“栈内”。初始化 $low[x]=dfn[x]=++tim$
• 2. 扫描从 $x$ 出发的每条边 $（x,y）$
  • (1)如 $y$ 没有被访问过，则说明 $（x,y）$ 是树边，递归访问 $y$ , 从 $y$ 回溯以后， $low[x]=min(low[x],low[y]);$
  • (2)若 $y$ 被访问过并且 $y$ 在栈中，则令 $low[x]=min(low[x],dfn[y])$
• 3. 从 $x$ 回溯之前，判断是否有$low[x]=dfn[x]$ .若成立，则不断从栈中弹出节点，直至 $x$ 出栈，标记 $x$ 栈外。从栈中弹出的点就构成了一个强连通分量。

核心代码如下：

//c[i] 点i属于哪一个强连通分量
void tarjan(int x)
{
	dfn[x]=low[x]=++tim;
	st[++top]=x;ins[x]=1;  //入栈并标记x的状态为栈中
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(dfn[y]==0)  //y未访问
		{
			targin(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])   //y已访问且在栈内
			low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		++tot;
		int y;
		do{
			y=st[top--];
			ins[y]=0;   //标记y的状态为栈外
			c[y]=tot;
		}while(x!=y);
	}
} 

例 P3387 【模板】缩点

【题意简介】给定一个带点权的有向图，求一条路径，使得路径上点权和最大。点和边可以重复经过，对于任意路径求出路径上点权之和最大。

【分析】一个强连通分量内任意点可达，那么点权要全部算上，直接强连通分量缩点，图变为“有向无环图-DAG”，在 DAG 上求最长路径，动态规划求解，可以记忆化搜索或者利用拓扑序求解。

【重要性质】利用 Tarjan 求有向图强连通分量，对强连通分量依次标号，对应的标号从大到小就是缩点后 DAG 的拓扑序。

本题可以直接在拓扑序上求 DAG 上求最长路径

参考代码：点击

学习完毕

{{ select(1) }}

• YES
• NO