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

标签：连通边双个点割边 DFS 2024 Day ZR 分量

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\) 到 \(n\) 的顺序去DFS，到达每个点时将其入栈，得到每个点的出栈序列 \(q_1, q_2, \ldots, q_n\)，即为缩点后的拓扑序.
按照 \(q_n,\ldots, q_1\) 的顺序去 DFS 原图就是一个合法的顺序。

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

按照 \(1\) 到 \(n\) 的顺序去 DFS 原图，得到每个点的出栈序列 \(q\).
按照 \(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\).

标签：连通,边双,个点,割边,DFS,2024,Day,ZR,分量
From： https://www.cnblogs.com/Heartquakes/p/18312678