强连通分量&缩点——Tarjan

对于一个有向图，当我们进行DP等过程时，可能会由于环的存在而导致程序陷入死循环，造成答案的错误甚至是RE，这时便需要通过缩点的方式消除掉环。

强连通分量

强连通

对于一个有V个点、E条边的有向图G（可以表示为: \(G<V,E>\) ）,如果一个点集V’满足 \(V’⊆V\) 且点集中所有的点都可互相到达，则称 V’ 是强连通的。

而强连通分量的意思则是满足强连通定义的最大点集

例如在这一张图里的强连通分量为{1}, {2,3,4}, {5,6,7}

注意：一个孤立的单点也算是一个强连通分量哦！

那么怎么理解最大点集的含义呢？看这张图

在这一个有向图中，显然点集{1,2,3}和点集{2,3,4}都是满足强连通的定义的，但是由于④号点也可以通过 \(4->2->3->1\) 的路径到达①号点，因此这个图的强连通分量应该是{1,2,3,4}。

看完这里，你应该明白强连通分量的定义了！

Tarjan求强连通分量

前置知识：对图DFS时的一些概念

首先，Tarjan的基础是一个DFS操作

在DFS的过程中，如果不访问已经访问过的节点，那么DFS得到的是一棵树。如果访问已经访问过的点并就此返回，则可以遍历整张图，并且你得到的是：一棵树，两种非树边。

在这张图中：黑色的边即是我们在DFS中得到的树边；蓝色的边指向一个在DFS得到的树中不是起点的祖先的点，红色的边指向起点在DFS得到的树中的祖先。

我们通常 ~~用两个字来形容这种人，叫做“赌怪”！~~ 将DFS得到的树的边叫做树边，将蓝色的边称为横叉边，将红色的边称为后向边。

很显然，树是没有环的，而横叉边也是不可能产生环的，能够导致环形成的只有后向边，因此一个环中一定有至少一个后向边。

下面我们来考虑一下DFS的过程

核心思想

我们用一个栈 \(s\) 来维护强连通分量，模拟一下DFS的过程。

DFS到①号点，①号点进栈。栈为{1}
DFS到②号点，②号点进栈。栈为{1，2}
DFS到③号点，③号点进栈。栈为{1，2，3}
DFS到④号点，④号点进栈。栈为{1，2，3，4}
DFS到②号点，②号点已经访问过了，而且②号点还在栈中，说明②号点是④号点的祖宗，这是一条后向边。因此产生了一个环，从②到④的路径上的点全都是环上的，将他们逐个弹出并记录。然后再去遍历其他的点。栈为{1}
DFS到⑤号点，⑤号点进栈。栈为{1，5}
DFS到⑥号嗲，⑥号点进栈。栈为{1，5，6}。⑥号点出度为0，肯定是一个强连通分量了，从栈中弹出。
DFS到⑦号点，⑦号点进栈。栈为{1，5，7}
DFS到⑥号点，⑥号点已经访问过了但不在栈中，说明⑥号点不是⑦号点的祖先，这是一条横叉边，不理。

由此一来，这个图就遍历完了。并且在遍历过程中已经记录下了所有的强连通分量。又由于每个点只会被访问 \(1\) 次，所以Tarjan表面上看是一个DFS的玄学复杂度，实际上复杂度是 \(O(N+E)\) 的。

具体做法

先考虑一个我们前面没有考虑的问题：对刚才的图片稍事修改

如果一个图上有如左图所示的两条后向边。那么在按照上面的过程进行操作时，很有可能深搜到④号点后搜到了②号点，电脑一看，哦？强连通分量Get，于是直接记录并弹栈，导致下方的⑧号点被忽略。因此我们需要进行一些适当的改动。

为了实现算法的正确性，我们需要以下的变量：
\(dfn[x]\)：(DFS Number) 作为一个搜索的时间戳，记录搜索的顺序
\(low[x]\)：记录点 \(x\) 所属的强连通（并最终记录所属的强连通分量）
\(in[x]\)：记录点 \(x\) 是否在栈中

*注：图中没有写的地方就是较上一状态没有变化的

后面的代码实现，我们用例题来看。

代码实现

例题： https://www.luogu.org/problem/P2341

#include<stack>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=5e4+10;
bool in[M];
int n,m,cnt,now,num;
int head[M],dfn[M],low[M],id[M],all[M],out[M];
struct edge{
	int to,nxt;
}e[M];
stack<int> S;

int Read(){//快读
	int x=0;
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Add(int x,int y){//链式前向星建边
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}

void Tarjan(int x){
	dfn[x]=low[x]=++now;
	S.push(x);//点x进栈
	in[x]=1;//记录点x是否在栈中
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){//若该点没有访问过，则深搜该点，结束后更新low[x]
			Tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(in[v]) low[x]=min(low[x],dfn[v]);//如果该点已被访问，更新low[v]
	}
	int k;
	if(low[x]==dfn[x]){//弹出栈并记录
		num++;
		while(x!=k){
			k=S.top();
			S.pop();
			in[k]=0;
			id[k]=num;
			all[num]++;
		}
	}
}

int main(){
	n=Read(),m=Read();
	for(int i=1;i<=m;i++){
		int x=Read(),y=Read();
		Add(x,y);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
	for(int k=1;k<=n;k++)
		for(int i=head[k];i;i=e[i].nxt){
			int v=e[i].to;
			if(id[v]!=id[k]) out[id[k]]++;//遍历每一个点并记录出度
		}
	now=0;
	for(int i=1;i<=num;i++)
		if(!out[i]){//只有所有牛都喜欢的牛才是明星，因此只能有最多一个出度为0的强连通分量
			if(now) return puts("0")&&0;
			now=i;
		}
	printf("%d\n",all[now]);
	return 0;
}

( •̀ ω •́ )

Tarjan缩点

缩点的操作本质上和求强连通分量差别不大。

看例题： https://www.luogu.org/problem/P3387

题目概述：有一有向图允许你多次经过一个点，首次经过一个点时可以获得他的点权，求可取得得最大点权和。

怎么做呢？缩点！

缩点是什么？为什么可以缩点？

缩点：把环缩成一个点，其点权为环上所有点得点权和，出边入边为所有环上点的出边入边组成的集合。

为什么可以缩点：因为环上每一个点都是可以多次访问的，且每一个点的权值都只能获得一次，又点权都是非负的，所以选取环上所有点是最优的。因此缩点后的点权可以视为环上所有点的和。

代码实现

用Tarjan求出强连通分量后，用一个点来代表缩点后的点，而 \(fa[]\) 数组记录其他的点缩点后属于哪一个点。当Tarjan()执行结束后，按照前面记录的 \(fa[]\) 数组重新建立新的图（这会是一个DAG），再进行简单的计算最长路即可！

#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=1e5+10;
bool vis[M];
int n,m,cnt,now,top,ans;
int a[M],s[M],fa[M],in[M],dis[M],dfn[M],low[M],head[M],head2[M];
struct edge{
	int from,to,nxt;
}e[M],ed[M];

int Read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Add(int x,int y){
	cnt++;
	e[cnt].to=y;
	e[cnt].from=x;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}

inline void Add_New(int x,int y){
	cnt++;
	ed[cnt].to=y;
	ed[cnt].from=x;
	ed[cnt].nxt=head2[x];
	head2[x]=cnt;
}

void Tarjan(int x){
	s[++top]=x;
	vis[x]=1;
	dfn[x]=low[x]=++now;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]) Tarjan(v),low[x]=min(low[x],low[v]);
		else if(vis[v]) low[x]=min(low[x],low[v]);
	}
	if(dfn[x]==low[x]){
		int tmp;
		while(tmp=s[top--]){
			fa[tmp]=x;
			vis[tmp]=0;
			if(tmp==x) break;
			a[x]+=a[tmp];
		}
	}
}

void Topo(){
	queue<int> Q;
	for(int i=1;i<=n;i++)
		if(fa[i]==i&&!in[i]){
			Q.push(i);
			dis[i]=a[i];
		}
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		for(int i=head2[u];i;i=ed[i].nxt){
			int v=ed[i].to;
			dis[v]=max(dis[v],dis[u]+a[v]);
			in[v]--;
			if(!in[v]) Q.push(v);
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
}

int main(){
	n=Read(),m=Read();
	for(int i=1;i<=n;i++)
		a[i]=Read();
	for(int i=1;i<=m;i++){
		int x=Read(),y=Read();
		Add(x,y);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
	cnt=0;
	for(int i=1;i<=m;i++){
		int x=fa[e[i].from],y=fa[e[i].to];
		if(x!=y){
			Add_New(x,y);
			in[y]++;
		}
	}
	Topo();
	printf("%d\n",ans);
	return 0;
}

完✌