Graph
强连通分量
有向图的 DFS 生成树主要有 4 种边(不一定全部出现)
- 树边(tree edge):示意图中以黑色边表示,每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边(back edge):示意图中以红色边表示(即 $7 \to 1$),也被叫做回边,即指向祖先结点的边。
- 横叉边(cross edge):示意图中以蓝色边表示(即 $9 \to 1$ ),它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先。
- 前向边(forward edge):示意图中以绿色边表示(即 $3 \to 6 $),它是在搜索的时候遇到子树中的结点的时候形成的。
Tarjan
Tarjan 算法求强连通分量
在 Tarjan 算法中为每个结点 $u$ 维护了以下几个变量:
-
$dfn_u $深度优先搜索遍历时结点 $u$被搜索的次序。
-
$low_u$ $u$子树中 所能回溯的 最早的节点
一个结点的子树内结点的 dfn 都大于该结点的 dfn
从根开始的一条路径上的 dfn 严格递增,low 严格非降
时间复杂度
$O(n+m)$
模板
constexpr int N = 2e5 + 10;
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 SCC 的编号
int sz[N]; // 强连通 i 的大小
vector<vector<int>> G;
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1LL;
for (auto &v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sc;
while (s[tp] != u) {
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
}
例题
Acw1174 受欢迎的牛
每一头牛的愿望就是变成一头最受欢迎的牛。
现在有 $N$ 头牛,编号从 $1$ 到 $N$,给你 $M$ 对整数 $(A,B)$,表示牛 $A$ 认为牛 $B$ 受欢迎。
这种关系是具有传递性的,如果 $A$ 认为 $B$ 受欢迎,$B$ 认为 $C$ 受欢迎,那么牛 $A$ 也认为牛 $C$ 受欢迎。
你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。
第一行两个数 $N,M$;
接下来 $M$ 行,每行两个数 $A,B$,意思是 $A$ 认为 $B$ 是受欢迎的(给出的信息有可能重复,即有可能出现多个 $A,B$)。
输出被除自己之外的所有牛认为是受欢迎的牛的数量。
code
// AcWing 受欢迎的牛
// https://www.acwing.com/problem/content/1176/ 2024-02-09 22:01:34
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
constexpr int N = 2e5 + 10;
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 SCC 的编号
int sz[N]; // 强连通 i 的大小
vector<vector<int>> G;
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1LL;
for (auto &v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sc;
while (s[tp] != u) {
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
}
int n, m;
void solve() {
cin >> n >> m;
G.resize(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--, y--;
G[x].emplace_back(y);
}
for (int i = 0; i < n; i++)
if (!dfn[i]) tarjan(i);
vector<int> out(sc + 1);
for (int i = 0; i < n; i++) {
for (auto v : G[i]) {
if (scc[v] != scc[i]) {
out[scc[i]]++;
}
}
}
int cnt0 = 0, ans = 0;
for (int i = 1; i <= sc; i++) {
if (not out[i]) {
if (not cnt0)
ans += sz[i];
else
goto no;
cnt0++;
}
}
cout << ans << "\n";
goto end;
no:
cout << "0\n";
goto end;
end:
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
Acw367 学校网络
一些学校连接在一个计算机网络上,学校之间存在软件支援协议,每个学校都有它应支援的学校名单(学校 $A$ 支援学校 $B$,并不表示学校 $B$ 一定要支援学校 $A$)。
当某校获得一个新软件时,无论是直接获得还是通过网络获得,该校都应立即将这个软件通过网络传送给它应支援的学校。
因此,一个新软件若想让所有学校都能使用,只需将其提供给一些学校即可。
现在请问最少需要将一个新软件直接提供给多少个学校,才能使软件能够通过网络被传送到所有学校?
最少需要添加几条新的支援关系,使得将一个新软件提供给任何一个学校,其他所有学校就都可以通过网络获得该软件?
第 $1$ 行包含整数 $N$,表示学校数量。
第 $[2,N+1]$ 行,每行包含一个或多个整数,第 $i+1$ 行表示学校 $i$ 应该支援的学校名单,每行最后都有一个 $0$ 表示名单结束(只有一个 $0$ 即表示该学校没有需要支援的学校)
输出两个问题的结果,每个结果占一行。
code
// AcWing 学校网络
// https://www.acwing.com/problem/content/369/ 2024-02-09 22:34:40
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
constexpr int N = 2e5 + 10;
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc; // 结点 i 所在 SCC 的编号
int sz[N]; // 强连通 i 的大小
vector<vector<int>> G;
void tarjan(int u) {
low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1LL;
for (auto &v : G[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sc;
while (s[tp] != u) {
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
scc[s[tp]] = sc;
sz[sc]++;
in_stack[s[tp]] = 0LL;
--tp;
}
}
int n, m;
void solve() {
cin >> n;
G.resize(n + 1);
for (int i = 1; i <= n; i++) {
int x;
while (cin >> x, x) G[i].emplace_back(x);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
vector<int> in(sc + 1), out(sc + 1);
for (int i = 1; i <= n; i++)
for (auto v : G[i])
if (scc[v] != scc[i]) in[scc[v]]++, out[scc[i]]++;
int src = 0, des = 0;
for (int i = 1; i <= sc; i++) {
if (not in[i]) src++;
if (not out[i]) des++;
}
cout << src << "\n";
if (sc == 1)
cout << 0 << "\n";
else
cout << max(src, des) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
双连通分量
在一张连通的无向图中,对于两个点 $u$ 和 $v$
如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说 $u$ 和 $v$ 边双连通。
在一张连通的无向图中,对于两个点 $u$ 和 $v$
如果无论删去哪条点(只能删去一个,且不能删 $u$ 和 $v$)都不能使它们不连通,我们就说 $u$ 和 $v$ 点双连通。
边双连通具有传递性,点双连通 不 具有传递性,反例如下
DFS 找桥并判断边双连通
如上图所示,黑色与绿色边为树边,红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径,我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖,黑色的树边不被 任何 非树边覆盖。
我们如何判断一条边是不是桥呢?显然,非树边和绿色的树边一定不是桥,黑色的树边一定是桥。
如何用算法去实现以上过程呢?首先有一个比较暴力的做法,对于每一条非树边,都逐个地将它覆盖的每一条树边置成绿色,这样的时间复杂度为 $O(nm)$
怎么优化呢?可以用差分。对于每一条非树边,在其树上深度较小的点处打上 -1
标记,在其树上深度较大的点处打上 +1
标记。然后 $O(n)$ 求出每个点的子树内部的标记之和。对于一个点 $u$,其子树内部的标记之和等于覆盖了$u$ 和 $u$ 的父亲之间的树边的非树边数量。若这个值非 $0$,则 $u$ 和 $u$ 的父亲之间的树边不是桥,否则是桥。
用以上的方法 $O(n+m)$ 求出每条边分别是否是桥后,两个点是边双连通的,当且仅当它们的树上路径中 不 包含桥。
DFS 找割点并判断点双连通
如上图所示,黑色边为树边,红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径。
考虑一张新图,新图中的每一个点对应原图中的每一条树边(在上图中用蓝色点表示)。对于原图中的每一条非树边,将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块(这在上图中也用蓝色的边体现出来了)。
这样,一个点不是割点,当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。两个点点双连通,当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都属于同一个连通块。
蓝点间的连通关系可以用与求边双连通时用到的差分类似的方法维护,时间复杂度$O(n+m)$。
后续会补充 图论的 相关知识 ……
新年快乐!
新年快乐宝宝!
Orz