【C++】Tarjan算法

强连通分量

在有向图中，如果某一个子图的任意两点都是连通的则该子图是一个强连通分量。

T a r j a n Tarjan Tarjan算法有好几种，都是以 T a r j a n Tarjan Tarjan命名的，这里讲的 T a r j a n Tarjan Tarjan指求强连通分量的 T a r j a n Tarjan Tarjan算法，他以深度优先搜索的方式对图进行染色，进而求得强连通分量。

在一个顶点数为 n n n的图中， T a r j a n Tarjan Tarjan算法需要维护一个顶点栈和几个数组。

1. s t a c k   S stack S stack S表示顶点栈。
2. d f n [   ] dfn[ ] dfn[ ]数组， d f n [ i ] dfn[i] dfn[i]表示第 i i i个顶点的深度搜索次序。
3. l o w [   ] low[ ] low[ ]数组， l o w [ i ] low[i] low[i]表示顶点 i i i回溯时所能回溯到的最小 d f n dfn dfn。
4. v i s i t [   ] visit[ ] visit[ ]数组， v i s i t [ i ] visit[i] visit[i]表示顶点 i i i是否在栈中。
5. c o l o r [   ] color[ ] color[ ]数组， c o l o r [ i ] color[i] color[i]表示顶点 i i i在哪一个强连通分量，相同的强连通分量染色相同。

void Tarjan(int u){
	dfn[u]=low[u]=++cnt;//初始化dfn=low
	S.push(u);//顶点u入栈
	visit[u]=1;
	for(int i=head[u];i;i=last[i]){//遍历u的所有边
		int v=to[i];//v是以u为起点的边的终点顶点
		if(!dfn[v]){//如果还没有访问过v
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(visit[i]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		color[u]=++sum;//颜色+1，用相同的颜色对同一个连通分量染色
		visit[u]=0;//标记为未访问
		while(S.top()!=u){
			color[S.top()]=color[u];
			visit[S.top()]=0;//标记为未访问
			S.pop();
		}
	}
}

T a r j a n Tarjan Tarjan在除了有向图中可以求强连通分量，在无向图中还可以求割点和割边(桥)。

割点：无向图中去掉某一个点及其连接的边会破坏其连通性的点。

割边：去掉无向图中某一条边会破坏连通性的边。

割边连接的点必为割点，但是割点连接的边不一定是割边。

使用 T a r j a n Tarjan Tarjan算法求割点，若有边 u → v uto v u→v，如果 l o w [ v ] > = d f n [ u ] low[v]>=dfn[u] low[v]>=dfn[u]则说明 v v v无法连接到比 u u u更早的点，说明 u u u是割点。特别的，根节点无法通过此关系判断是否为割点，根节点需要判定子树大于等于 2 2 2则为割点。

void Tarjan(int u,int fa){
	int child=0;//子树个数
	dfn[u]=low[u]=++cnt;//初始化dfn=low
	for(int i=head[u];i;i=last[i]){//遍历u的所有边
		int v=to[i];//v是以u为起点的边的终点顶点
		if(!dfn[v]){//如果还没有访问过v
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&u!=root) cut[u]=1;//记录割点
		}else if(dfn[u]>dfn[v]&&v!=fa){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(u==root&&child>=2) cut[u]=1;
}

判断割边，只需要将上述代码的if(low[v]>=dfn[u]&&u!=root)改为if(low[v]>dfn[u]&&u!=root)即可求割边数量。