之前有学过双联通分量相关知识……

直到前几天学长讲课才发现自己可能学了假的Tarjan

这里做一个remake

预备知识

桥（割边）：如果去掉，图的联通块个数会增加的边

割点（割顶）：如果去掉，图的联通块个数会增加的点

DFS树：将一个图DFS遍历所得到的树

非树边：不在DFS树上的边

边双联通分量：任意两点可以通过两条不同路径（边不重复）互达的子图

点双联通分量：任意两点可以通过两条不同路径（点不重复）互达的子图

于是有这样的性质：

非树边只会存在于DFS树的点与祖先之间
一个点（割点）可能属于多个点双联通分量
一条边只属于确定的一个边双联通分量

边双联通分量

考虑非树边对DFS树的影响，有以下结论：

非树边及其在DFS树上覆盖的路径属于同一边双联通分量
边双联通分量缩点后整个图必然是森林

边双联通分量的Tarjan算法

找桥

记录\(dfn[x]\)表示x入栈的时间戳，\(low[x]\)为x可达的所有点中最小的dfn

那么，DFS树边\(u\rightarrow v\)是桥当且仅当\(low[v]>dfn[u]\)

这样我们就得到了找桥的Tarjan算法

void tarjan(int x,int fa){
	low[x]=dfn[x]=++times;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!dfn[son[j]]){
	 	tarjan(son[j],x); low[x]=min(low[x],low[son[j]]);
	 	if (low[son[j]]>dfn[x]) isb[j]=isb[j^1]=1;
	 }else if (son[j]!=fa) low[x]=min(low[x],dfn[son[j]]);
}

找边双联通分量

我原来的做法是：不经过桥，把整个图再遍历一次，每个联通块是边双

后来发现这简直蠢爆了

其实可以直接用强连通分量那套栈处理的方法

但是要注意：由于找到桥才判定边双，一定不要忘了根节点，可以结束后把栈清空！！

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++times;stk[++stk[0]]=x;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!dfn[son[j]]){
	 	Tarjan(son[j],x); low[x]=min(low[x],low[son[j]]);
	 	if (low[son[j]]>dfn[x]){
	 		BCC++;
	 		while (stk[stk[0]]!=son[j]) id[stk[stk[0]--]]=BCC;
	 		id[stk[stk[0]--]]=BCC;
		}
	 }else if (son[j]!=fa) low[x]=min(low[x],dfn[son[j]]);
}
//......
for (int i=1;i<=n;i++)
    if (!dfn[i]) {Tarjan(i,0); BCC++;while (stk[0]) id[stk[stk[0]--]]=BCC;}

点双联通分量的Tarjan算法

找割点

同样记录\(dfn\)和\(low\)

u是割点条件是存在\(u\rightarrow v\)，使得\(low[v]\ge dfn[u]\)

但是根节点需要特判——仅当根有多个儿子时，根才是割点

void Tarjan(int x,int fa){
	dfn[x]=low[x]=++times;int sum=0;bool suc=0;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!dfn[son[j]]){
	 	Tarjan(son[j],x);low[x]=min(low[x],low[son[j]]);
	 	if (low[son[j]]>=dfn[x]) suc=1;sum++;
	 }else if (son[j]!=fa) low[x]=min(low[x],dfn[son[j]]);
	g[x]=(fa&&suc||!fa&&sum>1);
}

找点双联通分量

和边双类似，用栈记录

点双联通分量缩点一般使用圆方树，所以Tarjan时直接建边

同样存在根节点的问题

inline void Tarjan(int x,int fa){
	dfn[x]=low[x]=++times;stk[++stk[0]]=x;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!dfn[son[j]]){
	 	Tarjan(son[j],x); low[x]=min(low[x],low[son[j]]);
	 	if (low[son[j]]>=dfn[x]){
	 		BCC++; add(x);
	 		while (stk[stk[0]]!=son[j]) add(stk[stk[0]--]);
		}
	 }else if (son[j]!=fa) low[x]=min(low[x],dfn[son[j]]);
}
//......
for (int i=1;i<=n;i++)
    if (!dfn[i]) {Tarjan(i,0); BCC++;while (stk[0]) add(stk[stk[0]--]);}

大概就好了吧……

linkfqy

A link to the past.

双联通分量小结+Tarjan模板整理