APTX Blog

A Moe Blog Set Up By APTX

C/C++:Tarjan算法求有向图强连通分量

文章目录[隐藏]

笔记

1、出度:以顶点v为起点的弧的数目

入度:顶点v为终点的弧的数目

2、如果在有向图G中,有一条<u,v>有向道路,则v称为u可达的,或者说,从u可达v。

3、强连通图:若有向图G的任意两个顶点都互相可达,则称图 G是强连通图,如果有向图G存在两顶点u和v使得u不能到v,或者v不能到u,则称图G是强非连通图。

4、强连通分量:如果有向图G不是强连通图,他的子图G2是强连通图,点v属于G2,任意包含v的强连通子图也是G2的子图,则称G2是有向图G的极大强连通子图,也称强连通分量。

5、极大强连通子图(强连通分量)解释:一个图的强连通子图,并且加入任何一个不在它的点集中的点都会导致它不再强连通。

6、强连通分量里边的任意两个点,都是互相可达的。

算法解析

1、Tarjan算法,是一个基于Dfs(深搜)的算法,假设我们要先从0号节点开始Dfs,我们发现一次Dfs我门能遍历整个图,而且我们发现,在Dfs的过程中,我们深搜到 了其他强连通分量中,那么我们Dfs之后如何判断哪个和那些节点属于一个强连通分量呢?

之所以用DFS就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图,就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。

2、首先引入两个数组

int dfn[]; //点搜索的次序编号
int low[]; //每个点在这颗树中的,最小的子树的根

3、Tarjan算法在搜索过程中把没有Tarjan过的点入栈并将该节点的dfn[i] = low[i] = ++dfs_num(也就是设成他自己),然后以这个节点为树根再进行搜索,当一颗子树搜索完毕时回溯,并在回溯时比较当前节点和目标节点的LOW值,将较小的LOW值赋给当前结点的LOW,这样可以保证每个节点在以其为树根的子树的所有节点中LOW值是最小的。如果回溯时发现当前节点DFN[i]==LOW[i],就将栈中当前结点以上的节点全部弹栈,这些点就组成了一个强连通分量。还要注意一点是,当目标节点进行过Tarjan但还在栈中,就拿当前节点LOW值与目标节点DFN值比较,把更小的赋给当前结点的LOW。

①对于从没访问过的节点:加入栈中让其DFN[i]=LOW[i]=++dfs_num,让vis[i]=1表示该点入栈了。这类点的标志是!DFN[i]&&!vis[i]。

②对于访问过但不在栈中的节点(!vis[i])直接回溯即可,因为既然该节点访问过了又不在栈中,就必定属于另一个强连通分量。这类点的标志是DFN[i]&&!vis[i]。

②对于访问过且在栈中的节点,比较当前节点LOW值和目标节点DFN值,将较小的赋给当前结点LOW值然后回溯。这类点的标志是DFN[i]&&vis[i]。

算法模板

评测:洛谷:P2863

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;


const int MAXN = 100005; 
const int MAXM = 500005;

struct node {
	int next,to;
} e[MAXN];

int cnt,num,n,m,dfn[MAXN],low[MAXN],head[MAXN],ans;
int cut[MAXN];
int all;
bool vis[MAXN];

stack< int > s;

void add(int ,int );
void work();
void Tarjan(int );

int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;++i) {
		int from,to;
		cin >> from >> to;
		add(from,to);
	}
	work();
	return 0;
}

void add(int from,int to) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	head[from] = cnt;
}

void work() {
	for(int i = 1;i <= n;++i)
		if(!dfn[i]) Tarjan(i);
	for(int i = 1;i <= all;++i) if(cut[i] > 1) ans++;
	cout << ans << endl;
}

void Tarjan(int u) {
	dfn[u] = low[u] = ++num;
	s.push(u);
	vis[u] = true;
	for(int i = head[u];i;i = e[i].next) {
		int v = e[i].to;
		if(!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(vis[v]) low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]) {
		all++;
		while(s.top() != u) {
			int k = s.top();
			s.pop();
			vis[k] = false;
			cut[all]++;
		}
		s.pop();
		cut[all]++;
		vis[u] = false;
	}
}

 

参考:

https://blog.csdn.net/mengxiang000000/article/details/51672725

https://blog.csdn.net/qq_34374664/article/details/77488976

https://www.cnblogs.com/reddest/p/5932153.html

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注