APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年8月26日 1530点热度 0人点赞 0条评论

笔记

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

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ HTML Tarjan 图论 强连通分量 模板 洛谷 算法
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
C/C++线性筛素数的三种方法 #动漫#升起的烟花,从下面看?还是从侧面看? 1080P Manjaro 17.1.0+版本双系统安装后无引导的解决方法 #C/C++#裴蜀定理(貝祖等式) #NOIP提高组#模板整理 一个健康的社会不应该只有一种声音
标签聚合
动漫 OI ST C++ 洛谷 HTML 日常 C/C++
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang