Tarjan-526互联

强连通分量

求解强连通分量 \(tarjan\) 算法

对于一个点，维护两个量：\(\text{low,dfn}\).

整个过程是在 dfs 中进行的，会生成一颗 dfs 生成树，所以下面的讲述中可能会牵扯到一些树的定义；
我们会制作栈，记录访问的节点，当找到一个 \(\text{scc}\) 的时候将栈弹出元素进行处理。

其中 \(\text{dfn}\) 表示这个点的 \(\text{dfs}\) 访问顺序，\(\text{low}\) 表示这个点最早可以访问到的点，形式化地，这个点可以到达的深度最小的点。

一些显著的特征：当 \(\text{low=dfn}\) 的时候可以找到一个 \(\text{scc}\)，顺着栈找就行了。

更加详细地，\(\text{low}\) 小于等于 \(\text{dfn}\) ，因为这个点至少可以访问到自己。而 \(\text{low}\) 可以顺着 \(\text{dfs}\) 迭代。

典型应用：缩点

可以将处于相同强连通分量的点缩成一点，让原图 \(\mathcal{G}\) 缩成一个 \(DAG:\) \(\mathcal{T}\) 这样做方便于处理一些问题。

code

namespace Graph{
	std::vector<int> G[N],T[N];
	int col[N],stack[N],dfn[N],low[N],val[N],a[N];
	int f[N];
	int top,tot;
	int n,m,Cnt;
	std::bitset<N> vis;
	void Init_Input(void){
		n=R(),m=R();
		for(int i=1;i<=n;++i)
			a[i]=R();
		for(int i=1;i<=m;++i){
			int ai=R(),aj=R();
			G[ai].add(aj);
		}
	}
	void Tarjan(int u){
		dfn[u]=low[u]=++tot;
		stack[++top]=u;
		vis[u]=true;
		for(int v:G[u]){
			if(!dfn[v]) Tarjan(v),low[u]=std::min(low[v],low[u]);
			else if(vis[v])  low[u]=std::min(low[u],dfn[v]);
		} if(dfn[u]==low[u]){
			++Cnt;
			while(stack[top]!=u){
				col[stack[top]]=Cnt;
				val[Cnt]+=a[stack[top]];
				vis[stack[top]]=0;
				top--;
			}
			col[stack[top]]=Cnt;
			val[Cnt]+=a[stack[top]];
			vis[stack[top]]=0;
			top--;
		}
	}
	int ans=0;
	void Run(void){
		Init_Input();
		for(int i=1;i<=n;++i)
			if(!dfn[i]) Tarjan(i);
		for(int i=1;i<=n;++i){
			for(int v:G[i])
				if(col[i]!=col[v])
					T[col[i]].add(col[v]);
		}
		for(int i=Cnt;i;--i){
			f[i]+=val[i];
			ans=std::max(ans,f[i]);
			for(int v:T[i]) f[v]=std::max(f[v],f[i]);
		}
	}
	void Output(){ IO::W(ans);putchar('\n'); }
}
int main(){ Graph::Run();Graph::Output(); }