Tarjan 算法思想求强连通分量及求割点模板（超详细图解）

约定不等于承诺〃 2022-11-21 03:47 191阅读 0赞

### 割点定义 ###

在一个无向图中，如果有一个顶点，删除这个顶点及其相关联的边后，图的[连通分量][Link 1]增多，就称该点是割点，该点构成的集合就是割点集合。简单来说就是去掉该点后其所在的连通图不再连通，则该点称为割点。  
若去掉某条边后，该图不再连通，则该边称为桥或割边。

若在图G中（如下图），删除uv这条边后，图的连通分量增多，则u和v点称为割点，uv这条边称为桥或割边。  
![在这里插入图片描述][2020102922363344.png_pic_center]  
显然，有割点的图不是[哈密尔顿图][Link 2]。

--------------------

### Tarjan算法求强连通分量 ###

##### 1、概念 #####

Tarjan算法是一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。

首先要了解几个**概念**：①连通图：在**无向图**中，**任意两点**可互相到达，称为连通图。②强连通图：在**有向图**中，**任意两点**可相互到达，称为强连通图。③弱连通图：将**有向图**看作无向图时，是连通图，则称为弱连通图。④强连通分量：在**有向图**中，若他的某个**子图**是强连通图，这该子图称为他的强连通分量。

##### 2、主要思想 #####

Tarjan算法的**核心**是DFS，在Tarjan中给了两个很重要的参数（时间戳）---- dfn\[x\]数组和low\[x\]数组。**dfn\[x\]** 是指第一次访问x结点的时间，**low\[x\]** 是指x结点可以回溯到的最早的时间点。在Tarjan中，DFS要先递归下一结点，然后再访问自己结点。

给定一个全局变量times，是一个访问时间值，每次访问到某一个新结点时，就给他一个新的时间点times++，dfn就是第一次访问到他的这个times，然后low需要去修改更新，判断能回溯到的最早的时间点。这里存储每个结点是用的栈这个数据结构，给一个instack来判断某结点是否在栈中。

##### 3、伪代码 #####

下面看看伪代码就能很快地理解了：

//主函数中 ** 伪代码 **
    main()
    { 
    	for(int i = 1;i <= n;i++)	//循环每一个点
    		if(dfn[i] == 0)		//如果该点的dfn值等于0说明没被访问过，就去访问他
    			tarjan(i);
    }

//tarjan算法中 ** 伪代码 **
    tarjan(x)	//访问x结点
    { 
    	Stack.push(x);		//先将x结点入栈
    	instack[x] = true;	//记录x结点入栈
    	dfn[x] = low[x] = times++;	//x结点的第一次访问时间就是times，可回溯的最早的时间也暂定为他自己，后面再更新
    	for(y = 1;y <= n;y++)	//循环x能走到的每一个结点
    	{ 
    		if(g[x][y])	//如果x到y有路
    		{ 
    			if(dfn[y] == 0)		//y结点没被访问过的情况
    			{ 
    				tarjan(y);	//先访问下一个y结点，再访问自己
    				low[x] = min(low[x],low[y]);	//访问自己，自己能走到y结点，所以就可以用y结点的low值和自己的low值取最小值
    			}
    			else if(y instack)	//如果y已经被访问过了，且y在栈中，说明y和自己
    				low[x] = min(low[x],low[y]);
    		}
    	}
    	if(dfn[x] == low[x])	//如果一个点的dfn和low值相同，这个点就是根
    	{ 
    		cnt++;		//ans是强连通分量的个数
    		int v;
    		do
    		{ 
    			v = Stack.top();
    			belong[v] = cnt;	//belong数组是统计v属于第几个强连通分量
    			num[cnt]++;		//num数组是统计第cnt个的强连通分量包含的点的个数
    			cout << v << " ";	//把同一个强连通分量的点打印在一行
    			instack[v] = false;	//出栈就更新他的出栈情况
    			Stack.pop();	//计算完的点出栈
    		}
    		while(v != u);	//使用do while结构就是为了先执行，后判断，使得根也计算上
    		cout << endl;
    	}
    }

**原理：** 如果一直dfs回到了之前访问过的某个点，那么这几个点就能构成一个环，必定是一个强连通分量。若某点的dfn数组和low数组值相同，说明这个点回溯回不到之前的点了，这个点肯定就是根结点了，我们就开始把栈里这之前的结点弹出来计算。  
![eg][]

##### 4、完整代码模板 #####

#include<iostream>
    #include<cstring>
    #include<stack>
    using namespace std;
    const int N = 1010,M = 10010;
    
    int n,m,cnt,times = 1;
    int e[M],ne[M],h[M],idx;
    int dfn[N],low[N],belong[N],num[N];
    stack<int> Stack;
    bool instack[N];
    
    void add(int a,int b)
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void tarjan(int u)
    { 
    	Stack.push(u);
    	instack[u] = true;
    	dfn[u] = low[u] = times++;
    	for(int i = h[u]; ~i;i = ne[i])
    	{ 
    		int v = e[i];
    		if(!dfn[v])
    		{ 
    			tarjan(v);
    			low[u] = min(low[u],low[v]);
    		}
    		else if(instack[v])
    			low[u] = min(low[u],low[v]);
    	}
    	if(dfn[u] == low[u])
    	{ 
    		cnt++;
    		int v;
    		do
    		{ 
    			v = Stack.top();
    			cout << v << " ";
    			belong[v] = cnt;
    			num[cnt]++;
    			instack[Stack.top()] = false;
    			Stack.pop();
    		}while(v != u);
    	}
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		add(a,b);
    	}
    
    	for(int i = 1;i <= n;i++)
    		if(!dfn[i])
    			tarjan(i),cout << endl;
    	
    	cout << "强连通分量个数:" << cnt << endl;
    	cout << "belong: ";
    	for(int i = 1;i <= n;i++)
    		cout << belong[i] << " ";
    	cout << "每个强连通分量中点的个数: ";
    	for(int i = 1;i <= cnt ;i++)
    		cout << num[i] << " ";
    
    	return 0;
    }

时间复杂度：O(n+m)

--------------------

### Tarjan算法求割点 ###

##### 1、主要思想 #####

DFS树  
dan\[ x \]数组：DFS中，x实际被访问的时间点  
low\[ x \]数组：DFS中，x通过无向边，可回溯到的最早时间点

方法：和上面求强连通分量方法相似，在我们求出dfn和low数组后，我们判断某个点x是不是割点，有如下两种判断方法：  
![eg][eg 1]  
注：在case 2中，因为我们得到的是DFS生成树，所以不存在A和B有边的情况，若A和B右边，则DFS时，B就是A的左节点了。

下面是判断桥的情况：  
![eg][eg 2]  
注：在无向图中对儿子到父亲这条边不做处理，如果更新了儿子到父亲这条边，这low\[y\]一定会更新成dfn\[x\]，因此就无法判断了。

##### 2、代码模板 #####

/* *给定无向图，求割边、割点数目和边、点信息 */
    #include<iostream>
    #include<cstring>
    #include<stack>
    #include<vector>
    using namespace std;
    const int N = 1010,M = 10010;
    
    int n,m,times = 1;	//n个点，m条边，times时间戳
    int e[M],ne[M],h[M],idx;	//链式前向星建边
    int dfn[N],low[N],addblocks[N];	//addblocks[x]数组是存删掉x点后增加的连通块数目
    bool instack[N],iscut[N],isbridge[N],cut,bridge;	//iscut[x]数组是存x点是不是割点，isbridge[x]数组是存索引为i的边是不是割边
    stack<int> Stack;
    vector<pair<int,int> > arr;		//arr数组是存割边都有哪些边（u -> v）
    
    void add(int a,int b)	//加边函数
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void tarjan(int u,int pre)	//u是当前点，pre是他的父亲
    { 
    	Stack.push(u);	//将u点入栈
    	instack[u] = true;	//标记u点在栈中
    	dfn[u] = low[u] = times++;	//更新dfn和low数组
    	int child = 0,flag = 0;		//child存孩子数量，flag判断走的这条边是不是儿子到父亲的边，保证不更新儿子到父亲的边
    	for(int i = h[u]; ~i;i = ne[i])	//循环u能走到的每个点
    	{ 
    		int v = e[i];
    		if(v == pre)	//如果v就是u的祖先pre，且flag == 0
    			continue;
    		if(!dfn[v])		//如果v点没访问过
    		{ 
    			child++;	//孩子数量加一
    			tarjan(v,u);	//访问v点
    			low[u] = min(low[u],low[v]);	//更新low值
    			if(low[v] > dfn[u])		//(u,v)边是桥的情况
    			{ 
    				bridge++;		//桥的数量加一
    				isbridge[i] = true;	//该条边记为桥
    				isbridge[i^1] = true;	//该条边的反向边也记为桥
    				arr.push_back({ u,v});	//将该点压入数组
    			}
    			if(u != pre && low[v] >= dfn[u])	//u点是割点的case1
    			{ 
    				if(!iscut[u])	//u第一次被标记为割点时
    					cut++;		//割点数加一
    				iscut[u] = true;	//u点记为割点
    				addblocks[u]++;		//删除u点，增加的连通块数量就加一
    			}
    		}
    		else
    			low[u] = min(low[u],low[v]);	//如果v点访问过，只更新low值即可
    	}
    	if(u == pre && child > 1)	//u是割点的case2
    	{ 
    		cut++;		//割点数量加一
    		iscut[u] = true;	//u记为割点
    		addblocks[u] = child-1;	//删除u增加的连通块数量就是孩子数量-1
    	}
    	instack[u] = false;	//记录u点出栈
    	Stack.pop();		//u点出栈
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		add(a,b);	//存无向图
    		add(b,a);
    	}
    	for(int i = 1;i <= n;i++)
    		if(!dfn[i])
    			tarjan(i,i);
    	cout << "cut = " << cut << endl;
    	cout << "bridge = " << bridge << endl;
    
    	return 0;
    }

##### 3、经典例题 #####

POJ 2117：求删除一个点后，图中最多有多少个连通块。

思路：tarjan算法，套模板，用图中原本的连通块数量加上删除割点后增加的连通块数量即可。

**代码模板：**

#include<iostream>
    #include<cstring>
    #include<stack>
    #include<vector>
    using namespace std;
    const int N = 10010,M = 100010;
    
    ...
    ...		//省略了上面相同的函数（ add()和tarjan() ）
    
    void solve()
    { 
    	int cnt = 0;
    	for(int i = 1;i <= n;i++)
    		if(!dfn[i])
    		{ 
    			tarjan(i,i);	//每tarjan一次说明有一个连通块
    			cnt++;			//记原图的连通块数量
    		}
    	int ans = 0;
    	for(int i = 1;i <= n;i++)
    		ans = max(ans,cnt+addblocks[i]);	//求最大值
    	cout << add << endl;
    }
    
    int main()
    { 
    	int a,b;
    	cin >> n >> m;
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b;
    		add(a,b);
    		add(b,a);
    	}
    
    	solve();
    
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F/290350
[2020102922363344.png_pic_center]: /images/20221120/2f391e45715c4d158af8cfd3ac09758f.png
[Link 2]: https://baike.baidu.com/item/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE
[eg]: /images/20221120/97e129266b2a4d5e9703918037828da8.png
[eg 1]: https://img-blog.csdnimg.cn/20201106115752682.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70#pic_center
[eg 2]: https://img-blog.csdnimg.cn/20201106121451889.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70#pic_center