【学习笔记】无向图的连通性

割点

定义: 在无向图连通图中,若把点 \(x\) 删去后整个图就不连通了,则 \(x\) 为割点(割顶)。

朴素方法: 每次删去一个点,然后判断图是否连通,时间复杂度为 \(O(n(n+m))\)

Tarjan 算法:

\(dfn_x\)\(x\)dfs 到的时间戳

\(low_x\):在 \(x\) 及以后被搜索的所有节点的 \(low\) 值和这些节点能到达的节点的 \(dfn\) 的最小值。

算法流程:

  1. \(1\) 号点开始遍历全图,对于遍历到的点 \(x\),记录它的 \(dfn_x\) 并将 \(low_x\) 的值赋为 \(dfn_x\)
  2. 接下来遍历 \(x\) 的所有子儿子 \(y\)
  • \(y\) 被访问过,则 \(low_x=\min(low_x,dfn_y)\)
  • \(y\) 没有被访问过,则先遍历 \(y\),接着 \(low_x=\min(low_x,low_y)\)

算法原理:

若点 \(x\) 不为割点,把所有没被访问过 \(y\) 放在 \(x\) 的“下方”,则必存在一条边从 \(y\) 连到 \(x\) 的“上方”且这条边在 \(x\) 的“右边”(不然应该先访问到这条边,或者说访问顺序在 \(x\) 之后),按照 \(low\) 数组的定义,则所以的 \(y\) 都满足 \(low_y<dfn_x\)

相反,若 \(x\) 为割点,则必有 \(low_y\ge dfn_x\)(注意,这里有等于号,因为若连到自己则仍为割点)。

特例:\(x\) 为根节点,则肯定存在 \(low_y\ge dfn_x\),判断不出割点,需要特判一下:如果 \(x\) 连接的联通块个数 \(\ge 2\),则其断开后这几个联通块会分开,则 \(x\) 为割点。

void tarjan(int k, int rt) {
	int cnt = 0;
	dfn[k] = low[k] = ++s;
	for (auto i : p[k]) {
		if (!dfn[i]) {
			cnt++;
			tarjan(i, rt);
			low[k] = min(low[k], low[i]);
			if (k != rt && low[i] >= dfn[k]) {
				if (!flag[k]) ans++;
				flag[k] = true;
			 } 
		}
		else low[k] = min(low[k], dfn[i]);
	}
	if (k == rt && cnt > 1) {
		if (!flag[k]) ans++;
		flag[k] = true;
	}
}

时间复杂度:\(O(n+m)\)

割边

定义: 在无向连通图中,若删去某条边,这个图就不连通了,则称这条边是割边(桥)。

Tarjan 算法:

求割边的算法与求割点的算法差不多,只是如果一条从 \(x\)\(y\) 的边为割边,则 \(y\) 不存在边能到 \(y\) 节点及其“上方”,即存在 \(y\) 使 \(low_y>dfn_x\)(这里和割点有所区别)。

代码实现时要注意,这里的边是双向边,为了每条边只访问一次,可以使用邻接链表来存图,这样在边表中一条边 \(e\) 的反向边为 \(e\oplus1\),注意这样存图边的编号得从 \(2\) 开始。

void tarjan(int k) {
	int cnt = 0;
	dfn[k] = low[k] = ++s;
	for (int i = head[k]; i; i = e[i].nxt) {
		if (vis[i]) continue;
		vis[i] = vis[i ^ 1] = true;
		if (!dfn[e[i].to]) {
			tarjan(e[i].to);
			low[k] = min(low[k], low[e[i].to]);
            if (low[e[i].to] > dfn[k])
			    bri[i] = bri[i ^ 1] = true;
		}
		else low[k] = min(low[k], dfn[e[i].to]);
	}
}

时间复杂度:\(O(n+m)\)

点双连通分量(v-Dcc)

定义: 无向图中极大的(不能往外扩张)不存在割点的连通图(割点是指“局部”的割点),其任意两点之间都存在不经过重复点的两条路径。

性质: 一个割点可以存在于多个点双连通分量中,非割点只能存在于一个点双连通分量中,否则其就不是“分量”。

求法: 同样是 Tarjan 算法,不过要开一个栈记录:遍历到 \(x\) 时便把 \(x\) 压入栈,若 \(x\) 为割点,则它通过当前点“吊”着的所有点都弹出(\(x\) 不弹出),而 \(x\) 则是由“吊”着它的点弹出。有个注意点,到 \(y\) 时只应弹出 \(y\) 吊着的这一串,而不是把 \(x\) 吊的所有点都弹出。

特例:\(x\) 为孤立点时,它自成一个点双连通分量。

void tarjan(int k) {
    q.push(k);
	dfn[k] = low[k] = ++s;
	int sum = 0;
	for (auto i : p[k]) {
		if (!dfn[i]) {
			sum++;
			tarjan(i);
			low[k] = min(low[k], low[i]);
			if (low[i] >= dfn[k]) {
				cnt++;
				int t;
				do {
                    t = q.top();
					ans[cnt].push_back(q.top());
					q.pop();
				}while (t != i);
				ans[cnt].push_back(k);
			}
		}
		else low[k] = min(low[k], dfn[i]);
	}
    if (k == rt && sum == 0) ans[++cnt].push_back(k);
}

时间复杂度:\(O(n+m)\)

边双连通分量

定义: 无向图中极大的(不能往外扩张)不存在割边的连通图,其任意两点之间都存在不经过重复边的两条路径。

性质: 割边可以不存在于任何边双连通分量中,非割边只能存在于一个边双连通分量中。

求法: 由于边双连通分量中不包含割边,那么就可以先跑一遍 Tarjan 标记出割边,然后 dfs,不经过割边跑出的联通块就是边双连通分量。

//省略 Tarjan 函数
void dfs(int k)
{
	ans[sum].push_back(k);
	vis[k] = true;
	for (int i = head[k]; i; i = e[i].nxt)
	{
		if (bri[i]) continue;
		int v = e[i].to;
		if (!vis[v]) dfs(v); 
	}
}

练习题

SP2878 KNIGHTS - Knights of the Round Table

洛谷 P3469 [POI2008] BLO-Blockade

洛谷 P2860 [USACO06JAN] Redundant Paths G

热门相关:洪荒二郎传   上神来了   戏精老公今天作死没   美容室:特殊服务4   上神来了