连通性相关

OI
图论

强连通分量 / SCC ​

定义 ​

强连通：有向图中，如果两个点能互相到达，称这两个点强连通。

强连通分量：一个极大的强连通子图。

一个有向图中，一个点属于一个强连通分量。反证：假设一个点属于两个强连通分量，那么这两个强连通分量可以合并为同一个。

求解 ​

使用 Tarjan 算法，定义 low 和 dfn，建立出 DFS 生成树，使用栈辅助求解：

  • 初始化 low 和 dfn，使其等于 xx 的 dfn 序
    • 枚举 xx 的出边，假设其连接 yy
      • 若 yy 已经遍历过
        • 若 yy 不在栈中，则跳过
        • 若 yy 在栈中，那么用 dfn[y] 更新 low[x]
      • 若 yy 未遍历过
        • 遍历 yy，用 low[y] 更新 low[x]
    • 若 low[x] 不超过 dfn[x]，说明栈中 x 直到栈顶的节点构成了一个强连通分量。

由于使用了栈，得到的 SCC 标号是逆拓扑序。

应用 ​

常用于将一些有向有环图进行缩 SCC 的操作，将其变为一个 DAG（有向无环图）以便于进行处理。

割点和桥 ​

定义 ​

割点定义为无向图中，删去这个点之后能使图不连通的点。

桥（或割边）定义为无向图中，删去这条边之后能使图不连通的边。

求解 ​

仍然使用 Tarjan 算法，类似地，定义 low 和 dfn，建立出 DFS 生成树：

  • 初始化 low 和 dfn，使其等于 xx 的 dfn 序

    • 枚举 xx 的出边，假设其连接 yy

      • 若 yy 已经遍历过，用 dfn[y] 更新 low[x]
      • 若 yy 未遍历过，则遍历 yy，用 low[y] 更新 low[x]

    • 若 low[x] 不超过 dfn[fa]，则 fa 为一个割点。

这个流程在 DFS 生成树的根不适用，需要特殊判断根的儿子数量（注意不是连边数量），若大于 1 则根是割点。

桥的求解类似，只要将判断条件 low[x]<=dfn[fa] 改为 low[x]<dfn[fa]，则边 (x，fa)(x，fa) 是一条割边。

注意如果有重边，则可能出现两条到父亲的边，需要记录从哪一条边来，另一条边可以更新 low。

割点代码：

Sample Code(c++)
c++
const int N = 2e4 + 5, M = 2e5 + 5;
struct Graph {
	int head[N], nxt[M], to[M], tot;
	void add(int u, int v) {
		nxt[++tot] = head[u];
		to[tot] = v;
		head[u] = tot;
	}
} G;
int dfn[N], low[N], dfn_cnt, rt_cnt;
bool is_cut[N];

void dfs(int x, int fa) {
	low[x] = dfn[x] = ++dfn_cnt;
	for (int i = G.head[x]; i; i = G.nxt[i]) {
		if (G.to[i] == fa) continue;
		if (dfn[G.to[i]]) {
			low[x] = min(low[x], dfn[G.to[i]]);
			continue;
		}
		if (!fa) ++rt_cnt;
		dfs(G.to[i], x);
		low[x] = min(low[x], low[G.to[i]]);
	}
	if (low[x] >= dfn[x]) {
		is_cut[fa] = true;
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		G.add(u, v);
		G.add(v, u);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			rt_cnt = 0;
			dfs(i, 0);
			is_cut[i] = (rt_cnt > 1);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; ++i) cnt += is_cut[i];
	cout << cnt << '\n';
	for (int i = 1; i <= n; ++i) {
		if (is_cut[i]) {
			cout << i << ' ';
		}
	}
	return 0;
}

双连通分量 ​

定义 ​

边双连通：在一张连通的无向图中，对于两个点 uu 和 vv，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 uu 和 vv 边双连通。

点双连通：在一张连通的无向图中，对于两个点 uu 和 vv，如果无论删去哪个点（只能删去一个，且不能删 uu 和 vv 自己）都不能使它们不连通，我们就说 uu 和 vv 点双连通。

极大的边双连通子图称为边双连通分量，极大的点双连通子图称为点双连通分量。

边双连通分量 ​

每一个点属于至多一个边双。

求解边双连通分量和强连通分量是几乎相同的，唯一区别是边是双向的，要记录来时的边（注意不是点，因为可能会有重边）不走，并且没有横叉边的情况，所以不用记录是否在栈中（返祖边必定在栈中）。

Sample Code(C++)
c++
const int N = 5e5 + 5, M = 4e6 + 5;
struct Graph {
	int head[N], nxt[M], to[M], tot;
	Graph() { tot = 1; }
	void add(int u, int v) {
		nxt[++tot] = head[u];
		to[tot] = v;
		head[u] = tot;
	}
} G;

int rt;
int dfn[N], dfn_cnt, low[N];
int sta[N], top;
vector<vector<int>> ans;
void dfs(int x, int from) {
	dfn[x] = low[x] = ++dfn_cnt;
	sta[++top] = x;
	for (int i = G.head[x]; i; i = G.nxt[i]) {
		if ((i ^ 1) == from) continue;
		if (dfn[G.to[i]]) {
			low[x] = min(low[x], dfn[G.to[i]]);
			continue;
		}
		dfs(G.to[i], i);
		low[x] = min(low[x], low[G.to[i]]);
	}
	if (low[x] == dfn[x]) {
		ans.push_back(vector<int>());
		while (sta[top + 1] != x) {
			ans.back().push_back(sta[top--]);
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		G.add(u, v);
		G.add(v, u);
	}
	for (int i = 1; i <= n; ++i)
		if (!dfn[i]) rt = i, dfs(i, 0);
	cout << ans.size() << '\n';
	for (auto i : ans) {
		cout << i.size() << ' ';
		for (auto j : i)
			cout << j << ' ';
		cout << '\n';
	}
}

点双连通分量 ​

有性质：

  1. 两个点双至多有一个公共点，并且公共点是割点，否则可以导出这两个点双可以合并。
  2. 一个点双中，dfn 序最小的是割点或树根。

考虑一个非根节点，若这个点是割点，那么它与到栈顶的节点形成了一个点双。

考虑一个根节点，若这个点是孤立点，则它是一个点双。否则它到栈顶的点也形成一个点双。

注意最后割点不能出栈，因为可能还有其余的点双包括这个点。

Sample Code(C++)
c++
const int N = 5e5 + 5, M = 4e6 + 5;

struct Graph {
	int head[N], nxt[M], to[M], tot;
	Graph() { tot = 1; }
	void add(int u, int v) {
		nxt[++tot] = head[u];
		to[tot] = v;
		head[u] = tot;
	}
} G;

int rt;
int dfn[N], low[N], dfn_cnt, sta[N], top;
vector<vector<int>> ans;
void dfs(int x, int from) {
	dfn[x] = low[x] = ++dfn_cnt;
	if (x == rt && !G.head[x]) {
		ans.push_back(vector<int>(1, x));
		return;
	}
	sta[++top] = x;
	for (int i = G.head[x]; i; i = G.nxt[i]) {
		if ((i ^ 1) == from) continue;
		if (dfn[G.to[i]]) {
			low[x] = min(low[x], dfn[G.to[i]]);
			continue;
		}
		dfs(G.to[i], i);
		low[x] = min(low[x], low[G.to[i]]);
		if (low[G.to[i]] >= dfn[x]) {
			ans.push_back(vector<int>());
			while (sta[top + 1] != G.to[i]) {
				ans.back().push_back(sta[top--]);
			}
			ans.back().push_back(x);
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		if (u == v) continue;
		G.add(u, v);
		G.add(v, u);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) rt = i, dfs(i, 0);
	}
	cout << ans.size() << '\n';
	for (auto i : ans) {
		cout << i.size() << ' ';
		for (auto j : i)
			cout << j << ' ';
		cout << '\n';
	}
}
欧拉路径与欧拉回路