本文主要是介绍【图论】强连通分量+tarjan算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

参考

[算法]轻松掌握tarjan强连通分量_邋遢大哥233

Pecco算法学习笔记(69): 强连通分量

acwing

强连通分量【Strongly Connected Components——简称SCC】

定义

强连通：在一张有向图G中，如果一个顶点u和另一个顶点v，既有从u到v的有向路径，也有从v到u的有向路径，则称这两个顶点具有强连通的关系。

强连通图：如果在一张有向图G中的任意两个结点都具有强连通的关系（都可以互相到达），则称这张有向图为强连通图。

极大强连通：将所有具有同一强连通关系的点全部包含在一张子图中。

强连通分量：若一张有向非强连通图具有极大强连通子图，称这张子图为强连通分量。

缩点：将强连通分量缩成一个点。

注：由于定义，我们可以将一张有向非强连通图划分成数个强连通分量，且由于极大属性的设定，所以分属于任意两个不同强连通分量的两个结点之间不具有强连通关系。

dfs序：按照dfs的搜索顺序，依次对经过的结点进行编号（被搜到的时间？），所得到这些结点的最终编号的序列。并且dfs生成的树叫做dfs生成树（有向无环图）。

dfs序越小说明这个结点越早被访问到。

在生成dfs生成树的实际过程中并不单单只具有生成树本身的树边，除此之外，还有三种类型的边。

1. 前向边：

   从某个点到它的某个子孙节点的边。

   比如结点1可先通过4再达到5（有中转站），而这时，1到5有一条从1指向5的有向边（从1到5的直通车），称这样子的一条有向边为前向边，由于前向边只是对连通起到一种替代的作用，所以一般不会对图的强连通的特性造成影响。

2. 反向边：反向边指的是由当前结点指向了已经被访问（已经具有dfs序）的结点。（而当前结点是必然是由这个已经被访问过的结点延伸过来的，因而，反向边是形成环的原因）

3. 横叉边：

   从某个点到一个既非它子孙节点、也非它祖先节点的边。

   横叉边有点像有一天你接到一个陌生人的电话，他说他是你的远方亲戚，而所谓的远方亲戚，就是从你和他的当前的辈分在族谱上向上追溯一定有一个共同的交点（最近公共祖先？），然后在连上这条横插边的时候，相当于会将他那边的祖先结点的信息也带了过来，因而有可能形成一个更大的强连通子图。

   注：连过去的点是已经具有dfs序（其实也就是说它已经被访问过了，他的dfs序小于当前这个结点的dfs序，这个特性是和反向边是一样的）。

由于只有反向边和横叉边会对强连通分量的形成起到影响，因而我们有这么一个结论，对于每个强连通分量，存在一个点是其他所有点的祖先。

并且将这个在强连通分量的祖先，叫做强连通分量的根。

对于强连通分量，我们一般会使用Tarjan算法。

Tarjan算法

Tarjan算法的预准备

dfn(p)数组：dfn(p)数组代表的是第p个结点在被访问到的时间点。

low(p)数组：low(p)数组定义为点通过有向边可以追溯到的最早的时间点

如果一些点通过low数组所映射到的值是一样的，这这些点能够组成强连通分量。

low数组的更新实际上是运用到了动态规划的思想。

最终的情况肯定是最末的一个结点去接触到了这个强连通分量的根节点，从而导致了这个最末的结点的low的值被更新为这个根节点的时间戳，并通过dfs的特性，将low的值不断会返回到上一层结点。

同时在不断递归回上一层的时候，是会回到根节点的位置的。

并且是在根节点遍历完所有的结点后才会去做关于这张强连通分量的结算的（这就保证了横叉边能够起到一定的作用）

st栈：搭配dfs的搜索特性，用来存储暂时可以形成强连通分量的一些点，若已经形成了强连通分量，则将会被弹出到栈外；若st栈中仍有元素的存在，则将这些元素全都弹出，单独再去组成一个强连通分量。

结合栈的特性，可以一次性处理好一个强连通分量，并且不会对其他的强连通分量造成影响。

处理

如果当前某个结点没有被访问(有可能图不是连通的)，就跑下dfs

for(int i=1;i<=V;i++)
    if(dfn[i]==0)
       DFS(i);

DFS(int u)
{
    stack.push(u);
    dfn[u]=low[u]=time++;
    for(点u所连接的边的点)
        如果这个点没有被访问过，则这条边是一般的树边
           DFS(v);
           low[u]=min(low[u],low[v]);//取min的重要性在于预防跑下去的不一定是强连通分量的情况，所以不能直接让
        如果这个点有被访问，且仍留在栈中（仍未组成一个强连通分量）
           low[u]=min(low[u],low[v]);
     /***结算部分***/
     if(dfn[u]==low[u])
     {
        stack.pop()直到u
        并把弹出的元素归到以u为根节点的强连通图的门下；
     }
}

tarjan算法需要的变量

1. 两个时间戳数组dfn和low，dfn代表的是这个点实际的到达的dfs的时间，low统计的是某个点能回溯到的最早时间戳的点的时间戳。

2. 一个栈st，用来存储当前仍未形成强连通分量的点

3. 一个bool数组in_st，用来判断当前要判断的点是否在栈中

4. id数组用来表示当前点属于哪一个强连通分量

5. 一个缩写变量scc_cnt,用来表示强连通分量有几个；一个size数组，用来表示当前的强连通分量里面有几个点。

   最终在结算的部分，先更新scc_cnt，一旦有一个点从栈弹出就size[scc_cnt]++;

6. 一个出度数组dout，用来记录每个连通分量的出度

缩点操作

for(int i=1;i<=n;i++)
   for(int j=h[i];~j;i=ne[i])
   {
       int k = e[j];
       int a = id[i],b = id[j];
       if(a!=b) dout[a]++;//将i所处在的强连通分量看成是一个点，并和其他的强连通分量产生关系，这里是指i所在的强连通分量所能够到达的其他强连通分量的个数。
   }

题目

tarjan的应用——缩点

AcWing 1174. 受欢迎的牛

本质：若一个点能够让这张图中的其他点通过路径来追求得到的话，那么这个点可以认为是受欢迎的。

同时如果这张图中如果存在两个及以上出度为0的点，那么答案就是0，因为出度为0的点都是无法欢迎对方的。

对于一个DAG图来讲，最受欢迎的点一旦是最后一个点。

但图并没有想象的那么简单，但我们可以通过tarjan算法将复杂的图转化成DAG图。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+100,M=5e4+100;
int n,m;
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],timestamp;
stack<int > st;
bool in_st[N];
int scc_cnt,id[N],dout[N],Size[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++timestamp;
	st.push(u);
	in_st[u]=true;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u]=min(low[j],low[u]);
		}
		else if(in_st[j])
            low[u]=min(low[j],low[u]);
	}

	if(dfn[u]==low[u])
	{	
		scc_cnt++;
		while(1)
		{
			int t=st.top();
			st.pop();
			Size[scc_cnt]++;
			if(u==t)
			{
				id[t]=scc_cnt;	
				in_st[t]=false;
				break;
			}
		
			id[t]=scc_cnt;	
			in_st[t]=false;
		
		}
	}
} 
int main()
{
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		  tarjan(i);
	}	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=h[i];~j;j=ne[j])
		{
			int v=e[j];
			if(id[i]!=id[v])
			   dout[id[i]]++;
		}
	}
	int dout0=0;
	for(int i=1;i<=scc_cnt;i++)
	{
		if(dout[i]!=0) continue;
		dout0++;
		if(dout0==2)
		{
			ans=0;
			break;
		}
		ans+=Size[i];
	}
	cout<<ans;
    return 0;
}

这篇关于【图论】强连通分量+tarjan算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！