【学习笔记】Tarjan之缩点

一、有向图强联通分量

• 在有向图中，如果同时存在从x到y和从y到x的有向路径，则称x和y强连通。
• 如果一张有向图中任意点对都强连通，那么称这张图是一个强连通图。
• 有向图的极大强连通子图为强连通分量。
• 图中的每个点只会属于一个强联通分量

二、Tarjan算法求强联通分量

• 原理是求出图的任意生成树，利用返祖边找环。

• 对一个点维护dfn[x]表示该点的dfs序，low[x]表示x不经过x的祖先能到达的最浅的祖先

• dfs时先将x压入栈中，然后遍历出边：
  树边：dfs孩子，用其low更新本身low
  返祖边：用其dfn更新本身low，注意如果是无向图中的父边不算返祖边

• dfs结束时若dfn[x]==low[x]则将当前栈中x以上的所有点和x统计成一个强联通分量

三、Tarjan缩点

模板
一个强连通分量自身不影响，把一个点算进答案，这个点所在的强连通分量也要进入答案
考虑缩点，tarjan跑出强连通分量，每个强连通分量缩成一个点，构成DAG，在DAG上跑DP
用记忆化比较方便

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], Index, dfn[maxn], low[maxn], top, vis[maxn], sta[maxn];
int dp[maxn], n, m, sum[maxn], val[maxn], x[maxn], y[maxn], tot, ans, color[maxn];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge) { y, head[x] }; head[x] = num; }

void tarjan(int u){
	dfn[u] = low[u] = ++Index;
	vis[u] = 1, sta[++top] = u;
	//赋值dfn，low
	//入栈
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else
		if (vis[v]) low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		++tot;
		while (sta[top + 1] != u) color[sta[top]] = tot, vis[sta[top]] = 0, sum[tot] += val[sta[top--]];
		//color表示强连通分量编号，vis表示是否在栈中,sum表示强连通分量权值和
	}
}

void dfs(int u){
	if (dp[u]) return;
	dp[u] = sum[u];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		dfs(v);
		dp[u] = max(dp[u], dp[v] + sum[u]);//这里是记忆化
	}
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) val[i] = read();
	for (int i = 1; i <= m; ++i){
		x[i] = read(), y[i] = read();
		addedge(x[i],y[i]);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i]) tarjan(i);
	num = 0;
	memset(head, 0, sizeof(head));
	for (int i = 1; i <= m; ++i)
		if (color[x[i]] != color[y[i]]) addedge(color[x[i]], color[y[i]]);//重新连边，一个强连通分量缩成一个点
	for (int i = 1; i <= tot; ++i)
		if (!dp[i]){
			dfs(i);
			ans = max(ans, dp[i]);
		}
	printf("%d\n", ans);
	return 0;
}