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

割点定义

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

若在图G中（如下图），删除uv这条边后，图的连通分量增多，则u和v点称为割点，uv这条边称为桥或割边。

显然，有割点的图不是哈密尔顿图。

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数组值相同，说明这个点回溯回不到之前的点了，这个点肯定就是根结点了，我们就开始把栈里这之前的结点弹出来计算。

4、完整代码模板

#include
#include
#include
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是不是割点，有如下两种判断方法：

注：在case 2中，因为我们得到的是DFS生成树，所以不存在A和B有边的情况，若A和B右边，则DFS时，B就是A的左节点了。

下面是判断桥的情况：

注：在无向图中对儿子到父亲这条边不做处理，如果更新了儿子到父亲这条边，这low[y]一定会更新成dfn[x]，因此就无法判断了。

2、代码模板

/*
*给定无向图，求割边、割点数目和边、点信息
*/
#include
#include
#include
#include
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 == 0continue;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点，增加的连通块数量就加一}}elselow[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
#include
#include
#include
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！