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

tarjan 求强连通分量

时间:2023-09-12 12:37:49浏览次数:28  
标签:tarjan int 连通 ++ ivoid dfn low 求强



for(int i=0;i<n;i++) //图可能是不连通的,因此要表里每个点
		if(!dfn[i])
			tarjan(i);
void tarjan(int u)
{
	int i,v;
	dfn[u]=low[u]=ntime++;
	z.push(u);
	f[u]=1;
	for(i=0;i<q[u].size();i++){
		v=q[u][i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(f[v]==1)
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
		while(1){
			v=z.top();
			z.pop();
			f[v]=0;
			ceng[v]=nceng;//分层,ceng[v]表示v点存在第cneng层
			if(v==u){
				nceng++;
				break;
			}
		}
}




标签:tarjan,int,连通,++,ivoid,dfn,low,求强
From: https://blog.51cto.com/u_16244339/7444299

相关文章

  • 强连通分量
    强连通图判定从一个点出发,可以遍历整张图,再将所有的边反向,从同一点出发,可以遍历整张图,则该图是强连通图Tarjan求有向图强连通分量\(\text{dfn[u]}\)表示点\(u\)的dfs序,\(\text{low[u]}\)表示点\(u\)可以走到的dfs序最小的点我们在dfs树上,当一个点的\(\text{low[u]}=\te......
  • tarjan强连通分量
    intscc[N],sc;//结点i所在scc的编号intsz[N]; //强连通i的大小//dfn(u)为搜到结点u时的次序编号//low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号//当dfn(u)=low(u)时,以u为根的搜索子树上的所有节点是一个强连通分量voidtarjan(intu){ dfn[u]=low[u]......
  • 华为SAN存储在Red Hat系统下的主机连通性FAQ
    1、建立iSCSI连接后,主机系统无法重启现象主机系统和存储系统建立iSCSI连接后,主机系统重启失败。根因分析主机停止iSCSI服务时,session没有关掉。解决方案主机系统重启前,请先停止iSCSI服务,然后再重启主机。2、替换LUN后无法更新LUN的信息现象当替换LUN的时候(前后两个LUN使......
  • 《北文的树形连通块dp》
    想看原文可以看这个对于一些问题,让我们数颜色数,要知道数颜色数这个东西非常的不好维护。往往我们四种解决方法:直接暴力数只数最后一个出现的(如果有什么性质的话)容斥,减去算重的将每个分开来计算贡献本文着重讲解第三种和第四种。......
  • 图解Spark Graphx基于connectedComponents函数实现连通图底层原理
    原创/朱季谦第一次写这么长的graphx源码解读,还是比较晦涩,有较多不足之处,争取改进。一、连通图说明连通图是指图中的任意两个顶点之间都存在路径相连而组成的一个子图。用一个图来说明,例如,下面这个叫graph的大图里,存在两个连通图。左边是一个连接图,该子图里每个顶点都存在路......
  • tarjan求点双连通分量
    边双连通分量见tarjan求边双连通分量部分参考lyd《算法竞赛进阶指南》前置知识给定无向连通图\(G=(V,E)\)割点:若对于\(x\inV\),从图中删去x及其连边,\(G\)分裂成两个及以上不相连子图,那么x是\(G\)的割点时间戳:在深度优先访问时按照每个节点第一次被访问的时间顺......
  • tarjan求边双连通分量
    本文仅为作者的一些学习笔记,内容可能具有局限性,比如并未就“点双连通分量”进行整理。部分参考lyd《算法竞赛进阶指南》前置概念桥(割边):若\(e\inE\),如果删去e后图分裂成两个子图,那么e这条边就为桥(割边)。时间戳:在深度优先访问时按照每个节点第一次被访问的时间顺序,依次......
  • Tarjan 求割点和桥
    欢迎批评指正!前置芝士割点:对于一个点\(u\),若删除\(u\)会使当前无向图中连通分量增多,我们就称\(u\)为该图的割点。桥(割边):同理,对于一条边\((u,v)\),若删除\((u,v)\)会使当前无向图中连通分量增多,我们就称\((u,v)\)为该图的桥。Tarjan求强连通分量Tarjan求割点设......
  • Tarjan 求强连通分量
    欢迎批评指正!前置芝士什么是强连通分量(\(\text{SCC}\))?强连通分量,一般指有向图的极大强连通子图,在这些子图中,所有点双向可达。dfs序:即dfs过程中访问点的顺序。dfs生成树:由dfs过程中访问的边组成的边集和原图的点集组成的树。树边,非树边:属于dfs过程中访问的边为......
  • hdu:Oil Deposits(dfs连通图)
    ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.......