首页 > 其他分享 >强连通分量tarjan

强连通分量tarjan

时间:2024-08-12 17:19:19浏览次数:12  
标签:tarjan int top 连通 colnum vis low 分量

引言

强连通分量本质上是处理一个有向有环图(如果在这样的图上搞事情可能会死循环)变成一个有向无环图
强连通分量上的点可以互相到达
所以针对一些问题(我也没搞明白究竟是哪种问题)例如:

给你一张有向图,每个点都有一个点权(不是边权了哦),且每一个点都可以经过任意多次,但是点权只能加一次,求这张图的最大权值

要是将最短路的模板改一下,会出现环t飞,所以先缩点然后再跑一遍最短路(改一下)

维护

vector<int> G[maxn];//存图
s[top]//栈,存放答案
int vis[maxn];//标记点是否在栈中
int dfn[maxn];//节点i的时间戳
int low[maxn];//节点i能够回溯到的最早位于栈中的节点。(子树的根,可以理解为并查集的“祖先”一类的东西)
int color[maxn];//每个点属于第几个强联通分量
int colornum;//强连通分量的个数
int cnt;//当前时间

求强连通分量操作

先将节点标号并入栈
先访问所有节点
如果访问到的节点没有被访问过则访问一下
然后用所有被访问到并且在栈内(因为如果不在栈内说明已经被弹出,不可能构成强连通分量)的节点更新自身的 \(low[]\) 数组
最后判断本节点是否为栈顶
如果是则将本强连通分量的所有元素弹出并染色
因为栈是先进先出原则所以不用担心有重叠问题

代码P2863

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int low[N],dfn[N],s[N],col[N],vis[N];
int cnt,top,u,v,n,m,colnum,ans;
vector<int>b[N];
void dfs(int x){
	dfn[x]=low[x]=++cnt;
	s[++top]=x;
	vis[x]=1;
	for(auto i:b[x]){
		if(!dfn[i])  dfs(i);
		if(vis[i])  low[x]=min(low[i],low[x]);//如果不在栈中说明他到达不了x,不可能构成强连通分量 
	}
	if(dfn[x]==low[x]){
		colnum++;
		int j=0;
		while(s[top]!=x){
			j=1;
			col[s[top]]=colnum;
			vis[s[top]]=0;
			top--;
		}
		col[x]=colnum;
		vis[x]=0;
		top--;
		if(j)  ans++;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])  dfs(i);
	}
	printf("%d",ans);
}

缩点操作

将所形成的各个强连通分量重新赋值并建边
形成新的有向无环图
针对于P2341的解析
因为喜欢可以传递
所以一个强连通分量中的牛都是互相喜欢的
所以进行缩点操作后的牛如果有且仅有一头牛它的出度为零
则证明缩点后的图是有向联通的
则出度为零的强连通分量的元素个数则为被所有牛喜欢的牛
我们考虑为什么出度不为零的牛不被所有牛喜欢
因为如果它指向的牛还有反过来指向它则它们就在同一个强连通分量中了
不符合我们已经缩点的事实

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int vis[N],dfn[N],s[N],low[N],col[N],id[N],c[N],num[N];
int top,u,v,cnt,ans,n,m,colnum;
vector<int>b[N];
void dfs1(int x){
	dfn[x]=low[x]=++cnt;
	s[++top]=x;
	vis[x]=1;
	for(auto i:b[x]){
		if(!dfn[i])  dfs1(i);
		if(vis[i])  low[x]=min(low[i],low[x]);
	}
	if(dfn[x]==low[x]){
		colnum++;
		while(s[top]!=x){
			vis[s[top]]=0;
			col[s[top]]=colnum;
			num[colnum]++;
			top--;
		}
		col[s[top]]=colnum;
		num[colnum]++;
		vis[x]=0;
		top--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		b[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])  dfs1(i);
	}
	for(int i=1;i<=n;i++){
		for(auto j:b[i]){
			if(col[i]!=col[j]){
				c[col[i]]++;
			}
		}
	}
	for(int i=1;i<=colnum;i++){
//		printf("i=%d id=%d %d %d\n",i,id[i],col[i],c[id[i]]);
		if(!c[i]){
			if(ans){
				printf("0");
				return 0;
			}
			ans=num[i];
		}  
	}
	printf("%d",ans);
}

标签:tarjan,int,top,连通,colnum,vis,low,分量
From: https://www.cnblogs.com/zcxnb/p/18355365

相关文章

  • 【Tarjan SCC 加边使得所有图联通 至少选取多少个点能图联通 】Network of Schools加
    [P2812校园网络【USACO]NetworkofSchools加强版大意:1.图G=(V,E)选几个点可以到达所有的点2.连多少条边可以让任意一个点出发到达其他所有点1思路:1.Tarjan跑一遍求SCC那些出度为0的点就是出发的所有点即din0的点的数量2.计算dout0的点的数量和din0的点的数量取max......
  • 使用python做页面,测试数据库连通性!免费分享!测试通过~
    免费分享刚刚写的一个小程序,测试通过没问题,解BUG也就花了半小时吧有更好的方法欢迎评论区推给我谢谢。importtkinterastkfromtkinterimportmessageboximportpymysqldefget_db_info(db_source):ifdb_source=='database1':hostname=e1.get()......
  • 强连通分量
    CF427CCheckposts#include<bits/stdc++.h>#definemid(((l)+(r))/2)usingnamespacestd;typedeflonglongll;typedeflongdoubleld;constllN=1e5+10,inf=1e18+10,mod=1e9+7;lln,m,a[N],tot,dfn[N],low[N];boolins[N];vector<ll>G[N];stack&......
  • 边分治维护强连通分量(CF1989F,P5163)
    这里的边分治和树上的点分治边分治不一样,是维护强连通分量用的,每条边有一个出现时间,通过将每条边按连通关系分流重新排列,从而维护每个时间点整张图的连通性。具体的,这个算法是维护这样的一类问题:n个点,m条边按时间顺序依次加入,每加入一条边,你需要回答一些问题,比如在这个时间点......
  • Tarjan 与连通性
    tarjan是一系列与图连通性相关的算法的统称,本文将总结常见的tarjan算法。并配合一定量的练习。无向图求割边割点割点:删掉后让整个图不联通的点。割边(桥):删掉后让整个图不联通的边。搜索树:对图进行dfs时经过的边的集合。容易发现其构成一棵树。搜索树上的边称为树边。时间......
  • Tarjan算法和连通性相关(三)
    上一篇博客我们介绍了割点和桥,本文我们继续学习与连通性有关的一些概念边双连通分量什么是边双连通分量?在一张连通的无向图中,对于两个点u和v,如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说u和v边双连通,边双联通分量是极大的边双连通子图怎么求边双连通......
  • Tarjan算法和连通性相关(二)
    上一篇博客我们介绍了强连通分量,本文我们继续学习与连通性有关的一些概念割点什么是割点?对于一个无向图,如果把一个点删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点我们画个图理解一下:在这个图中,如果我们把3这个点给删除掉,那么这张图就会被拆分成两个部......
  • Tarjan算法与连通性相关(一)
    昨天在打牛客多校的时候遇到了一道与连通性有关的图论题,笔者一眼就看出这题考察的知识点是Tarjan算法,但是笔者上次写Tarjan算法还是三年前的事情(太惭愧了qaq),于是笔者和队友在赛时花了一个小时时间学习了Tarjan算法成功通过了此题,故写下这篇博客进一步加深印象,同时也是分享自己对于......
  • 桥与边双联通分量
    板子和常识https://oi-wiki.org/graph/bcc/板子用的是tarjan算法2的思想只能跑无向图理论基础SCC部分对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个\(u\)使得$\texttt{dfn}_u=\texttt{low}_u$。该结点一定是在深度遍历的过程中,该连通分量中第一个......
  • 【笔记】图论:2-sat、连通性、欧拉回路选讲
    [AGC059C]GuessingPermutationforasLongasPossible(2-sat)这个东西十分智障,只需要对于所有\(a,b,c\),如果询问顺序是\((a,b),(b,c),(a,c)\),那么不能\(a<b<c\)或\(a>b>c\)。其它的情况(一条链)你一看发现肯定需要出现上述情况,那么这就是充要条件。你一看你直接对所......