Java教程

[学习笔记] 无向图和有向图的连通分量

本文主要是介绍[学习笔记] 无向图和有向图的连通分量,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 前言
  • 无向图
    • 割点
    • 点双连通分量
    • 边双连通分量

前言

之前每次需要计算强连通分量的时候都用的 \(\text{Kosaraju}\),主要是感觉 \(\rm Tarjan\) 好玄学,我的智商驾驭不了这个玩意儿。

但是,\(\rm Tarjan\) 真的太强大了!随便做道图论都有它!于是只有重学一遍,我真的是被逼的

无向图

割点

先上代码吧:

for(int i=1;i<=n;++i)
    if(!dfn[i]) tarjan(i,i);

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx;
	int son=0;
	for(int i=0;i<e[u].size();++i) {
		int v=e[u][i];
		if(v==fa) continue;
		if(!dfn[v]) {
			++son;
			tarjan(v,u);
			if((u^fa) and low[v]>=dfn[u])
				cut[u]=1;
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(u==fa and son>1) cut[u]=1;
}

定义 \(\text{dfn}_u\) 是遍历 \(u\) 的时间戳,\(\text{low}_u\) 是 \(u\) 在 不经过父亲 时能到达的时间戳最小的点的时间戳,初始时 \(\text{low}_u=\text{dfn}_u\)。我们先构建出一棵 \(\rm dfs\) 树,由于边是双向的,容易发现边只有树边与返祖边。这也是循环中的 if-else 判断。

那么当 \(u\) 通过树边连接到 \(v\) 时,如果 \(\text{low}_v\ge \text{dfn}_u\),就说明 \(v\) 子树中没有点可以不经过 \(u\) 到达上层,所以 \(u\) 是割点。需要注意的是,每个连通块的根都满足这一条件,但显然并不是所有根都是割点,我们需要额外判断:记录 \(son\) 表示根的 不经过根无法连通 的儿子的个数,那么当 \(son>1\),根即为割点。

为什么当 \(u\) 通过返祖边连接到 \(v\) 时,\(\text{low}_u\) 被 \(\text{dfn}_v\) 更新呢?首先强调一下 else 中还藏着一个 \(v\neq \rm fa\) 的判断。问题在于,用 \(\text{low}_v\) 更新并不能保证在返回时用树边更新 \(\text{low}_x\) 时(假设 \(x\) 是 \(v\) 的某个祖先)的用于更新的值不经过 \(x\) 的父亲。

很容易列举的反例是 \((x,y),(y,z),[z,x]\)(\([]\) 表示返祖边),如果 \(x\) 在进入 \(y\) 的子树之前进入另一个子树,更新了自己的 \(\rm low\) 且比自己的 \(\rm dfn\) 小,那么 \(\text{low}_y\leftarrow \text{low}_z\leftarrow \text{low}_x\),我们就会以为 \(y\) 可以不通过 \(x\) 往上。

点双连通分量

懂了割点之后,这个还是很好理解的。需要注意根是孤儿的情况,而且一个割点可能被多个点双连通分量包含。

此时根不一定是割点,但我们仍需要利用它将剩余的点塞进一个点双连通分量中。另外,while() 循环应到 \(v\) 停止而不是 \(u\),不然会塞进去一些另外的点。

for(int i=1;i<=n;++i)
    if(!dfn[i]) tarjan(i,i);

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx; stk[++tp]=u;
	if(u==fa and !head[u]) {
		dcc[++Dcc].push_back(u);
		return;
	}
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(v==fa) continue;
		if(!dfn[v]) {
			tarjan(v,u);
			if(low[v]>=dfn[u]) {
                dcc[++Dcc].push_back(u);
                while(stk[tp]^v)
                    dcc[Dcc].push_back(stk[tp--]);
                dcc[Dcc].push_back(stk[tp--]);
            }
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

若 \(u\rightarrow v\) 是一条返祖边,仍然是用 \(\text{dfn}_v\) 来更新,原因同上。需要注意 重边 的问题,这可能会使桥变成非桥。

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx;
	bool Vis = false;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,u);
			if(low[v]>dfn[u]) 
                then (u,v) is a bridge.
			low[u]=min(low[u],low[v]);
		}
		else if(v==fa and !Vis) Vis = true;
		else low[u]=min(low[u],dfn[v]);
	}
}

边双连通分量

此时不在判断 low[v]>dfn[u] 的时候求解,会漏算孤儿的情况。

/*
网上很多代码有 inStack 数组,不太明白用来干嘛...
*/
void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx; stk[++tp]=u;
	bool Vis = false; int dot;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!dfn[v]) {
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(v==fa and !Vis) Vis = true;
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++scc;
		do {
			bl[dot=stk[tp--]]=scc;
		} while(dot^u);
	}
}
这篇关于[学习笔记] 无向图和有向图的连通分量的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!