【2024-ZR-C Day 4】图论（1）

作者：Heartquakes，发表于 Sat Jul 20 2024。

1. 强连通分量

1.1. 定义

在有向图中，选取一个点集 $S$，若对于 $S$ 中的任意两点 $u, v$，都满足 $u$ 可以到达 $v$，则称 $S$ 是强连通的。

强连通分量是图中一个极大的强连通的点集。

性质：把一个有向图通过强连通分量缩点后，新的图是一个 DAG.

1.2. Kosaraju 算法

在无向图中，求解连通分量只需要按照 $1$ 到 $n$ 的顺序依次考虑每个点。 考虑到 $i$ 点时，如果 $i$ 点未被访问过，就说明找到了一个新的连通分量，从 $i$ 点开始 DFS 即可找到i所在的连通分量。

在有向图中，上述算法不成立。

假设 $A$ 和 $B$ 是两个不同的强连通分量，且 $A$ 可以到达 $B$，那么只有先访问 $B$，再访问 $A$，才能使得上述算法成立。 也就是说，遍历顺序要保证 $B$ 中至少有一个点排在所有 $A$ 中的点之前。 考虑缩点后得到的 DAG，每次应访问出度为 $0$ 的点，即按照拓扑序的逆序访问缩点后的所有节点。

Kosaraju 算法的思想：

1. 把图中所有边反向，再按照 $1$ 到 $n$ 的顺序去DFS，到达每个点时将其入栈，得到每个点的出栈序列 $q_1, q_2, \ldots, q_n$，即为缩点后的拓扑序.
2. 按照 $q_n,\ldots, q_1$ 的顺序去 DFS 原图就是一个合法的顺序。

因为把边反向与否不改变强连通分量，所以得到一个简化的算法：

1. 按照 $1$ 到 $n$ 的顺序去 DFS 原图，得到每个点的出栈序列 $q$.
2. 按照 $q_n\ldots q_1$ 的顺序去 DFS 反图，依次得到每个强连通分量。

#include <bits/stdc++.h>
using namespace std;

bool vis[N];
vector<int> g[2][N];
stack<int> stk;

void dfs1(int u)
{
	vis[u] = 1;
	for(auto v : g[0][u])
		if(!vis[v]) dfs1(v);
	q.push(x);
}

void dfs2(int u, int id)
{
	vis[u] = 0, bel[u] = id;
	for(auto v : g[1][u])
		if(vis[v]) dfs2(v, root);
}

int main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	for(int i = 1; i <= n; i++)
		if(!vis[i]) dfs1(i);
	while(!stk.empty())
	{
		int u = stk.top(); stk.pop();
		if(vis[u]) dfs2(u, ++idx);
	}
	return 0;
}

---

2. DFS 树

一张图的 DFS 树是在对其进行 DFS 时，所经过的所有有效边形成的树结构。

在构造题中，通常我们用到的是无向图的 DFS 树。

无向图的 DFS 树满足所有非树边都是返祖边。

---

3. 边双连通分量

3.1. 定义&性质

一个无向连通图边双连通，当且仅当对于任意两个点，存在两条不相交的路径。

边双连通分量是图中一个极大的边双连通的点集。

定义割边为：在无向图中，该边所在连通块不再连通的边。 边双连通的定义中，“存在两条不相交的路径”显然等价于“如果无论删去哪条边都不能使它们不连通”，故一个无向连通图边双连通的充要条件是没有割边。

一个无向图边双缩点后是一棵树，所有树边是割边。 （若缩点后不是一颗树，说明还存在环，则环上所有的点在一个边双内，这与边双连通分量“极大”的定义矛盾。）

3.2. 算法解析

由【3.1. 定义&性质】，求出所有边双连通分量只需求出所有割边，由割边断开后得到的一个连通块就是一个边双连通分量。

取原图的 DFS 树，只有树边有可能是割边。

一条非树边（由【2. DFS 树】的性质知，只可能是返祖边）会覆盖掉一条链上的树边，这些树边就会被 ban 掉，使用树上差分（或树剖）维护，剩下的边就是割边。

---

4. Boruvka 算法

一个神秘的 MST 求法。

维护一些连通块（初始都是单点），并进行若干轮连边。

每一轮中，找到每个连通块连向其它连通块的最小边（需要做不等离散化，以边权为第一关键字，以边的编号为第二关键字）并连上，这一条边一定会在 MST 中。 （可以根据 Kruscal 的流程证明。）

每轮连通块数量至少减半，最多进行 $O(\log n)$ 轮连边。 最劣时间复杂度 $O((n + m) \log n)$.

Boruvka 算法适合用来求完全图（或非常稠密图）的 MST.

---

5. 例题

5.1. CF555E Case of Computer Network

给定一张 $n$ 个点 $m$ 条边的无向图和 $q$ 组有向点对 $(s, t)$。 询问是否存在使得所有 $s$ 都能到达 $t$ 的无向图中每条边的定向方案。 $n,m,q \le 2 \times 10^5$.

有一个显然的结论：

在边双连通分量中可定向，使得内部构成强连通。

只需取边双中的 DFS 树，使树边向下，非树边向上即可。

则在本题中，若 $s, t$ 在同一边双，则不必考虑（一定可以）。 那么只需考虑 $s, t$ 在不同边双的情况。

考虑将原图按边双缩点成一颗树。 对于每个询问 $s, t$，在树上的路径一定为 $s$ 到根之间向上、根到 $t$ 之间向下。

可以使用树链剖分+线段树区间覆盖来做，做的过程中 check 当前要定向的边中是否有边已经被定了相反的方向。

5.2. CF1364D Ehab's Last Corollary

给定一个无向连通图和正整数 $k$，求一个大小为 $\lceil \frac{k}{2} \rceil$ 的独立集或大小不超过 $k$ 的环（求出任意一个即可）。

首先找到图中的最小环。

• 若环的大小不超过 $k$，则已经得到了解。
• 若环的大小大于 $k$：对环进行黑白染色，由狄利克雷抽屉原理，必然存在一个颜色全部相同的大小大于 $\lceil \frac{k}{2} \rceil$ 的独立集，从其中任选 $k$ 个点即可。

问题转化为如何求最小环。

对于一条非树边 $(u, v)$，定义 $w_{u, v} = |dep_v - dep_u|$. 找到图中 $w$ 最小的非树边，它和 $u, v$ 之间的所有树边构成最小环。

5.3. CF1103C Johnny Solving

给定一张 $n$ 个点 $m$ 条边的无向连通图，以及一个整数 $k$，保证每个点度数 $\ge 3$，你需要找到一个至少有 $\lceil \frac{n}{k} \rceil$ 个点的路径，或者找出 $k$ 个环，其中每个环的环长都不是 $3$ 的倍数，且每个环中至少有一个点在这 $k$ 个环里只出现一次。

任取一棵 DFS 树。

• 如果最大深度 $\lceil \frac{n}{k} \rceil$，则找到了路径。
• 否则，根据树的性质，至少有 $k$ 个叶子。 由题中“保证每个点度数 $\ge 3$”的限制知，对于每个叶子，其至少有两条返祖边。 任取其中两条，根据模 $3$ 的余数分讨后不难发现，一定存在一个包含这个叶子的环，满足其环长不是 $3$ 的倍数。

5.4. LG5811 [IOI2019] 景点划分

给定一个 $n$ 个点、$m$ 条边的无向连通图，以及三个整数 $a, b, c$，满足 $a + b + c = n$，你需要将 $n$ 个点分成三个集合 $A, B, C$，大小分别为 $a, b, c$，使得其中至少两个集合是连通的 (集合中的任意两个点能只经过该集合内的点互相到达)，或者报告无解。

不妨设 $a \le b \le c$，则让集合 $A, B$ 连通的限制一定是最松的。

考虑原图是树的情况。我们想找到一条边，让它两侧的点数分布尽量均匀。

考虑重心，找到所有以重心为根的子树中最大的一个，连接这棵子树与重心的边即为该边。有解当且仅当子树 $size \ge a$.