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

557 0 0

作者:happy_zero

割点

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

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

Tarjan 算法：

(dfn_x)：(x) 被 dfs 到的时间戳

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

算法流程：

从 (1) 号点开始遍历全图，对于遍历到的点 (x)，记录它的 (dfn_x) 并将 (low_x) 的值赋为 (dfn_x)。
接下来遍历 (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_yge dfn_x)（注意，这里有等于号，因为若连到自己则仍为割点）。

特例： 若 (x) 为根节点，则肯定存在 (low_yge 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) 的反向边为 (eoplus1)，注意这样存图边的编号得从 (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); 
	}
}