「学习笔记」tarjan 算法与强连通分量

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
说简单一点就是环，环内的点都在一个强连通分量里，单独一个点也算是强连通分量（自己可以到达自己）。

变量

int tim, sc;
int dfn[N], low[N], scc[N];
vector<int> son[N], st;

tim: 时间戳计数器；
sc: 强连通分量数量；
dfn: 时间戳；
low: 通过一条返祖边向上能到达的最靠上的点；
scc: 所属的强联通分量；
son[N]: 存图；
st: 栈；

过程

在这张图上
红色的边是返祖边，蓝色的边是横叉边，绿色的边是前向边，黑色的边是树边。
我们从一个点开始 dfs，给每一个节点打上时间戳，在没有遇到返祖边之前，low 值为这个点自己，该节点入栈，在栈中的节点都是还没有确定所属强连通分量的节点，出栈的节点是已经找到强连通分量的点

dfn[u] = low[u] = ++ tim;
st.push_back(u);

若搜到的下一个点还没有被打过时间戳，则说明这个点从没有被搜到过，先搜索，随后更新 low 值；倘若它被打了时间戳，但仍在栈中，说明当前这条边是返祖边，则要更新 low 值。

for (int v : son[u]) {
	if (!dfn[v]) {
		tarjan(v);
		low[u] = min(low[u], low[v]);
	}
	else if (!scc[v]) {
		low[u] = min(low[u], dfn[v]);
	}
}

这里有个小细节，在 !dfn[v] 的条件下，low[u] = min(low[u], low[v]);，而在 !scc[v] 的条件下，low[u] = min(low[u], dfn[v]);。
这是因为 !dfn[v] 的条件下，我们走的是树边或前向边，节点位置一定在该节点之下，子节点 \(v\) 能到达的最靠上的位置就是 \(u\) 能到达的最靠上的位置；而 !scc[v] 的条件下，我们走的是返祖边，节点位置在该节点上边，所以 low[u] = min(low[u], dfn[v]);，而不是 low[u] = min(low[u], low[v]);，因为 \(v\) 不是 \(u\) 的子节点，且 \(u\) 点不一定能通过一条返祖边到达 low[v]。
如果一个节点的 dfn 等于 low，那么，说明这个点走返祖边能到达的最靠上的点就是它自己，就树上来说，它就是这个强连通分量中最靠上的点，截止到目前为止，在这个节点之后入栈的点就都是这个强连通分量的点，自己可以画画图看看。

if (dfn[u] == low[u]) {
	scc[u] = ++ sc;
	while (st.back() != u) {
		scc[st.back()] = sc;
		st.pop_back();
	}
	st.pop_back();
}

完整代码：

void tarjan(int u) {
	dfn[u] = low[u] = ++ tim;
	st.push_back(u);
	for (int v : son[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!scc[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		scc[u] = ++ sc;
		while (st.back() != u) {
			scc[st.back()] = sc;
			st.pop_back();
		}
		st.pop_back();
	}
}

应用

• 缩点
  将每一个强连通分量缩成一个点，建出一个新图，这样原本有环的图就变成了一个 DAG（有向无环图），可以用来拓扑排序和 DP，缩点要维护原来环中的点的信息，如点权之类的。

for (int i = 1; i <= m; ++ i) {
	int u = e[i].u, v = e[i].v;
	if (lt[u] != lt[v]) {
		nson[lt[u]].push_back(lt[v]);
	}
}

• 2-SAT 问题
  判断是否有环来判断条件是否冲突。