Tarjan 复习小结

  • 总算把这几个东西策清楚了。

  • 在(Tarjan)算法里面，有两个时间戳非常重要，一个是(dfn)，意为深度优先数，即代表访问顺序；一个是(low)，意为通过反向边能到达的最小(dfn)，也就是最强反祖能力。

  • 注意，强联通分量只存在于有向图中，割点，桥，点双，边双是无向图的概念。

一、割点。

  • [x] 模板题

  • 割点：一个结点称为割点，当且仅当去掉该节点和其相关的边之后的子图不连通。

  • 针对无向图。

  • 首先我们考虑一个连通图（非连通图可以分别考虑连通块），我们从任意一个起点开始进行深度优先搜索，可以得到一棵树，并且这棵树中所有结点的子树之间不存在边，即没有跨越两棵子树的边

  • 考虑一下，如果存在，那么与深度优先搜索树的定义互相矛盾。

  • 于是有如下定理：
    在无向连通图(G)中，
    1、根结点(u)为割顶当且仅当它有两个或者多个子结点；
    2、非根结点(u)为割顶当且仅当u存在结点v，使得(v)与其所有后代都没有反向边可以连回(u)的祖先。可以简单写成(dfn_uleq low_v)

  • 贴个代码

void Tarjan(R i,R rt){
	R sum=0;dfn[i]=low[i]=(++cnt);
	for(R k=hd[i];k;k=nt[k]){
		if(!dfn[to[k]]){
			Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);
			if(i==rt)sum++;
			else if(low[to[k]]>=dfn[i])ans[i]=1;
		}
		else low[i]=min(low[i],dfn[to[k]]);
	}
	if(i==rt&&sum>1)ans[i]=1;
}

注意 在不联通图中，应当
for(R i=1;i<=n;++i)if(!dfn[i])Tarjan(i,i);
这样才能保证全部求到，注意根节点.

二、桥。

  • 针对无向图。
  • 桥的求法其实也是类似的，它的求法可以看成是割顶的一种特殊情况.
  • 当结点(u)的子结点(v)的后代通过反向边只能连回(v)，那么删除这条边((u, v))就可以使得图(G)非连通了。用(Tarjan)算法里面的时间戳表示这个条件，就是(low_v>dfn_u)。
  • 注意更新(low)时是特判不能使用来的反边。
  • 不需要单独考虑根节点的情况。
  • 贴个代码
void Tarjan(R i,R id){
	dfn[i]=low[i]=(++cnt);
	for(R k=hd[i];k;k=nt[k]){
		if(k==(id^1))continue; 无向图中，这样的边是不能被遍历的。
		if(!dfn[to[k]]){
			Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);
			if(low[to[k]]>dfn[i])G[++tot]=k; k这条边即为桥。
		}
		else low[i]=min(low[i],dfn[to[k]]);
	}
}

三、强联通和双联通一点区别。

  • 链接

  • 所谓双连通与强连通，最大的差别，也是最本质的差别就是后者适用于无向图中，而前者适用于有向图。至于两者的概念是一样的，就是图中有a点、b点，从a点可到达b点，同时从b点可到达a点。

四、强联通分量。

  • 而为了存储整个强联通分量，这里挑选的容器是栈。

  • 每次一个新节点出现，就进，如果这个点有出度就继续往下找。

  • 每次返回上来都看一看子节点与这个节点的(low)值，谁小就取谁，保证最小的子树根。

  • 如果找到(low==dfn)，说明这个节点是这个分量的根节点。

  • 最后找到分量的节点后，就将这个栈里，它们就组成一个全新的分量。

  • 具体实现的时候，如果这条边是往下的边，就用他的(low)去更新现在的(low)

  • 否则，如果这条边指向了栈内的点，就用他的(dfn)去更新现在的(low)

  • 为什么要特别判断是否是栈内的点呢？因为只有栈内的点才可以到达当前点。在有向图中，如果指向的点不在栈内，他也就无法到达当前点，不可能组成强联通。

  • 判断(low==dfn)是在(for)循环外面进行的。

  • 贴个代码

void Tarjan(R i){
	low[i]=dfn[i]=(++cnt),vis[i]=1,Q[++tp]=i;
	R p=tp;
	for(R k=hd[i];k;k=nt[k]){
		if(!dfn[to[k]])Tarjan(to[k]),low[i]=min(low[i],low[to[k]]);
		else if(vis[to[k]])low[i]=min(low[i],dfn[to[k]]);
	}
	if(dfn[i]==low[i]){
		tot++;
		for(R j=p;j<=top;++j)vis[Q[j]]=0,bel[Q[j]]=tot;
		tp=p-1;
	}
}

五、边双。

  • 其实就是一个求桥的过程。
  • 一个桥把联通块分成了两个部分，这两个部分是独立的两个边双。
  • 贴个代码
void Tarjan(R i,R id){
	dfn[i]=low[i]=(++cnt);
	for(R k=hd[i];k;k=nt[k]){
		if(k==(id^1))continue; 
		if(!dfn[to[k]]){
			Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);
			if(low[to[k]]>dfn[i])vis[k]=vis[k^1]=1; 标记
		}
		else low[i]=min(low[i],dfn[to[k]]);
	}
}
upd on 10.31
  • 另外一种写法：
  • 或者类似于有向图的强联通分量，区别在于：
  • 强制不走回头路。
  • 不需要考虑是否在栈内。
void Tarjan(R i,R op){
	low[i]=dfn[i]=(++cnt),Q[++tp]=i;R p=tp;
	for(R k=hd[i];k;k=nt[k]){
	    if(k==op^1)continue;
		if(!dfn[to[k]])Tarjan(to[k],k),low[i]=min(low[i],low[to[k]]);
		else low[i]=min(low[i],dfn[to[k]]);
	}
	if(dfn[i]==low[i]){
		tot++;
		for(R j=p;j<=top;++j)bel[Q[j]]=tot;
		tp=p-1;
	}
}

六、点双

  • 其实就是一个求割点的过程。
  • 一个割点把联通块分成了两个部分，这两个部分是独立的两个点双。
  • 贴个代码
void Tarjan(R i,R rt){
	R sum=0;dfn[i]=low[i]=(++cnt);
	for(R k=hd[i];k;k=nt[k]){
		if(!dfn[to[k]]){
			Tarjan(to[k],rt),low[i]=min(low[i],low[to[k]]);
			if(i==rt)sum++;
			else if(low[to[k]]>=dfn[i])ans[i]=1;
		}
		else low[i]=min(low[i],dfn[to[k]]);
	}
	if(i==rt&&sum>1)ans[i]=1;
}
  • 和割点的代码是一样的，只是最后(Dfs)找到所有点双，注意，一个割点会存在于多个点双内。

七、小清新水题。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Tyher/p/9843020.html