Tarjan's Algorithm

AisDaeun 19 2023-10-29

Tarjan算法求无向图割点割边

割点与割边的定义

给定无向连通图G = (V, E):

  1. 对于x \in V,若删去xG不再连通,则称xG的割点;

  2. 对于e \in E,若删去eG不再连通,则称eG的割边(桥)。

算法及实现

定义两个数组:

  1. dfn数组:按照dfs遍历的先后,给予每个点一个标记值,称作时间戳,记在dfn数组中;

  2. low数组:不经过搜索到点x的边,能够到达的最小时间戳,称作追溯值,记在low数组中。

时间戳比较好维护,而维护追溯值是一个难点。

求割点

首先给出代码,对照代码进行解释:

int dfn[N], low[N], num, root;
bool cut[N];
void tarjan(int x) {
	dfn[x] = low[x] = ++num;
	int flag = 0;
	for (int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x]) {
				flag++;
				if (x != root || flag > 1) cut[x] = true; 
			}
		}
		else low[x] = min(low[x], dfn[y]);
	}
}
  1. 从任意点出发,开始搜索。先记录当前点(记为点u)的时间戳dfn[u],然后令low[u] = dfn[u]。这是因为,一个点至少能够到达它自己,而它自己的子树的时间戳一定比它的时间戳要大。因此,该点的实际追溯值一定小于等于该点的时间戳。

  2. 遍历连接当前点的所有边。

  • 如果u通向的点(记为点v)的时间戳还没有求出来,则先去搜索点v。此时得到了点v的追溯值。如果v的追溯值比u的追溯值还小,说明v能不通过(u, v)而回到比u还靠前的点,则u也一定能不通过(u.father, u)到达之前的点。所以用v的追溯值更新u的追溯值。如果v的值大于等于u的时间戳,说明v除了(u, v)再没有回到u的父树的方法了(大于等于,说明还能够到达u。),那么u是一个割点。

  • 如果u通向的点v的时间戳已经被求出来了,说明这个点被访问过了。此时如果v的时间戳比u还小,根据定义,u能回溯到v。所以,用v的时间戳更新u的追溯值。

  • flag变量:对于根节点,所有除它以外的点都不能再回溯到比他靠前的时间戳了。然而,如果根节点的度数是1(也就是说,根节点是其他生成树的叶子结点),就不能被称之为割点。

求割边

int dfn[N], low[N], num;
bool bridge[M];
void tarjan(int x, int in_edge) {
	dfn[x] = low[x] = ++num;
	for (int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if (!dfn[y]) {
			tarjan(y, i);
			low[x] = min(low[x], low[y]);
			if (low[y] > dfn[x]) 
				bridge[i] = bridge[i ^ 1] = true;
		}
		else if (i != (in_edge ^ 1)) 
			low[x] = min(low[x], dfn[y]);
	}
}

与求割点的方法极其类似。

注意:与网上大部分代码不同,此处记录的是进入当前节点u的边的编号,而不是父节点的编号。这是因为,当图中有重边时,如果仅记录父节点的话,算法会跳过所有通往u.father的边。然而如果这种边有多个,该边一定不是桥。所以,仅记录父节点的编号无法处理有重边的情况。

此处有一个小trick:令边的编号初值为1,因为是无向图,每条边加两次,可以通过e \oplus 1快速求出该边对应的反边。

tarjan算法求无向图的双连通分量

双连通分量(DCC)的定义

边双连通图:无向连通图中,若任意两点间至少存在两条边不重复的路径,则称该图为边双连通图。边双连通图一定没有割边,因为图中去掉任意一条边后仍旧连通。

点双连通图:无向连通图中,若任意两点间至少存在两条点不重复的路径,则称该图为点双连通图。点双连通图一定没有割点,因为图中去掉任意一个点后仍旧连通。

定理:一张无向图是点双连通图,当且仅当图中顶点数不超过2,或图中任意两点都同时包含在至少一个简单环(不自交的环)中。

边双连通分量(e-DCC):无向图的极大边双连通子图。所谓“极大”,就是满足该性质的最大子图。

点双连通分量(v-DCC):无向图的极大点双连通子图。注意,不同的v-DCC可能包含同一个割点,且孤立点也是v-DCC。

算法及实现

求边双连通分量

非常简单。求完无向图的桥之后,由割边分隔开的每一个连通块都是一个边双连通分量。

求完割边之后,dfs染色即可。

模板题:洛谷 P8436

#include <bits/stdc++.h>
//#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	while (!isdigit(ch)) fl = ch == '-', ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return fl ? -x : x;
}
const int N = 5e5 + 10, M = 4e6 + 10;
int head[N], ver[M], next[M], tot;
void add(int u, int v) {
	ver[++tot] = v, next[tot] = head[u], head[u] = tot;
}
int n, m, root;
int dfn[N], low[N], num;
bool bridge[M];
void tarjan(int u, int in_edge) {
	dfn[u] = low[u] = ++num;
	for (int i = head[u]; i; i = next[i]) {
		int v = ver[i];
		if (!dfn[v]) {
			tarjan(v, i);
			low[u] = std::min(low[u], low[v]);
			if (low[v] > dfn[u])
				bridge[i] = bridge[i ^ 1] = true;
		} 
		else if (i != (in_edge ^ 1)) 
			low[u] = std::min(low[u], dfn[v]);
	}
}
bool vis[N];
int cnt;
std::vector<int> dcc[N];
void dfs(int u) {
	vis[u] = true;
	dcc[cnt].push_back(u);
	for (int i = head[u]; i; i = next[i]) {
		int v = ver[i];
		if (!vis[v] && !bridge[i]) dfs(v);
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	n = read(), m = read();
	tot = 1;
	rep(i, 1, m) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	rep(i, 1, n) if (!dfn[i]) tarjan(i, 0);
	rep(i, 1, n) if (!vis[i]) {
		++cnt;
		dfs(i);
	}
	std::cout << cnt << '\n';
	rep(i, 1, cnt) {
		std::cout << dcc[i].size() << ' ';
		for (int i : dcc[i]) std::cout << i << ' ';
		std::cout << '\n';
	}
	return 0;
}

边双连通分量缩点

把每一个边双连通分量缩成一个点,就能形成一个新的图。

方法也很简单,求完边双连通分量之后,重新建立一张图即可。

求点双连通分量

模板题:洛谷 P8435

#include <bits/stdc++.h>
//#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using std::cin;
using std::cout;
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	while (!isdigit(ch)) fl = ch == '-', ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return fl ? -x : x;
}
const int N = 5e5 + 10, M = 4e6 + 10;
int head[N], next[M], ver[M], tot;
void add(int u, int v) {
	ver[++tot] = v, next[tot] = head[u], head[u] = tot;
}
int dfn[N], low[N], num, root;
int stack[N], top, cnt;
std::vector<int> dcc[N];
bool cut[N];
void tarjan(int u) {
	dfn[u] = low[u] = ++num;
	stack[++top] = u;
	if (u == root && !head[u]) {
		dcc[++cnt].push_back(u);
		return;
	}
	int flag = 0;
	for (int i = head[u]; i; i = next[i]) {
		int v = ver[i];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				flag++;
				if (u != root || flag > 1) cut[u] = true;
				cnt++;
				int z;
				do {
					z = stack[top--];
					dcc[cnt].push_back(z);
				} while (z != v);
				dcc[cnt].push_back(u);
			}
		} 
		else low[u] = std::min(low[u], dfn[v]);
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	int n = read(), m = read();
	rep(i, 1, m) {
		int u = read(), v = read();
		if (u == v) continue;
		add(u, v), add(v, u);
	}
	rep(i, 1, n) if (!dfn[i]) {
		root = i;
		tarjan(i);
	}
	cout << cnt << '\n';
	rep(i, 1, cnt) {
		cout << dcc[i].size() << ' ';
		for (int i : dcc[i]) cout << i << ' ';
		cout << '\n';
	}
	return 0;
}

Tarjan算法求有向图强连通分量

定义

流图:给定有向图G = (V, E),若\exists r \in V,从r出发能够到达\forall v \in V,则称G是一个流图,r是流图的源点。

强连通图:给定有向图G = (V, E), 若\forall x, y \in V,既存在xy的路径,又存在yx的路径,则称G是强连通图。

强连通分量(SCC):有向图的极大强连通子图。

求有向图的强连通分量时,low数组的定义与之前有所不同:

算法及实现

模板题:洛谷 B3609

#include <bits/stdc++.h>
//#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using std::cin;
using std::cout;
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	while (!isdigit(ch)) fl = ch == '-', ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return fl ? -x : x;
}
const int N = 10010, M = 100010;
int head[N], next[M], ver[M], tot;
void add(int u, int v) {
	ver[++tot] = v, next[tot] = head[u], head[u] = tot;
}
int dfn[N], low[N], num;
int stack[N], c[N], top, cnt;
bool ins[N];
std::vector<int> scc[N];
void tarjan(int u) {
	dfn[u] = low[u] = ++num;
	stack[++top] = u, ins[u] = true;
	for (int i = head[u]; i; i = next[i])
		if (!dfn[ver[i]]) {
			tarjan(ver[i]);
			low[u] = std::min(low[u], low[ver[i]]);
		} 
		else if (ins[ver[i]]) 
			low[u] = std::min(low[u], dfn[ver[i]]);
	if (dfn[u] == low[u]) {
		cnt++; int y;
		do {
			y = stack[top--], ins[y] = false;
			c[y] = cnt, scc[cnt].push_back(y);
		} while (u != y);
	}
}
bool vis[N];
signed main() {
	std::ios::sync_with_stdio(false);
	int n = read(), m = read();
	rep(i, 1, m) {
		int u = read(), v = read();
		add(u, v);
	}
	rep(i, 1, n) if (!dfn[i]) tarjan(i);
	cout << cnt << '\n';
	rep(i, 1, n) if (!vis[c[i]]) {
		sort(scc[c[i]].begin(), scc[c[i]].end());
		for (int i : scc[c[i]]) cout << i << ' ';
		cout << '\n';
		vis[c[i]] = true;
	}
	return 0;
}