Tarjan强连通分量 学习笔记

定义

什么是强连通分量呢？
在有向图中，如果两个顶点能互相到达另一个点，则称两个顶点强连通。如果有向图的每两个顶点都强连通，称这个图是一个强连通图。有向图的极大强连通子图，称为强连通分量。
其实就是一个图中的一个极大的子图，这个子图里面的任何一个点都能到达其他的点。

算法实现

那么我们怎么求一个图的强连通分量呢？
我会暴力！
这里介绍一种线性算法内求出这个图的所有的强连通分量，这个算法由 Robert Tarjan 发明。

算法流程

定义 \(\operatorname{dfn}_i\) 为第 \(i\) 个点被搜到的顺序， \(\operatorname{low}_i\) 为第 \(i\) 个点能到达的点的最小的 \(\operatorname{dfn}\)
伪代码大概长这样：

void dfs(当前点){
    元素入栈;
    for( 枚举当前点可以到达的所有点 ){
        if(搜到的点没有访问过) dfs(搜到的点);
        if(搜到的点在栈中) 更新当前点的low;
    }
    if(当前点的low和dfn相等){
        弹出这个元素和它之上的元素;
        //弹出的元素属于同一个强连通分量之内
    }
}

证明：有什么好证明的，感性理解一下其实是显然的啊

代码实现

int n,m,u,v;
int head[maxn],nex[maxm],to[maxm],kkk;
#define add(x,y) to[++kkk]=y;\
nex[kkk]=head[x];\
head[x]=kkk
//链式前向星
int vis[maxn],dfn[maxn],low[maxn],cnt;
//vis代表这个点是否在栈中，cnt代表访问的点的个数
int scc[maxn],num;
//scc[i]代表i号点在第几个强连通分量内，num代表当前强连通分量的个数
typedef int type;
struct Stack{
	type data[maxn];
	int _top;
	void clear(){ _top=0; return; }
	void push(type x){ data[++_top]=x; return; }
	type top(){ return data[_top]; }
	void pop(){ _top--; return; }
	bool empty(){ return _top<=0; }
}s;//手写栈
void dfs(int x){
	s.push(x);
	vis[x]=1; low[x]=dfn[x]=++cnt;
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]])
	    	dfs(to[i]);
	    if(vis[to[i]])
		    low[x]=min(low[x],low[to[i]]);
	}
	if(low[x]==dfn[x]){
		scc[x]=++num; vis[x]=0;
		while(s.top()!=x){
			scc[s.top()]=num;
			vis[s.top()]=0;
			s.pop();
		}
		s.pop();
	}
	return;
}//dfs
void tarjan(){
	s.clear(); num=0;
	for(int i=1;i<=n;i++)
	    if(!dfn[i])
	        dfs(i);
	s.clear();
	return;
}