蒟蒻lhz2022的图论(tarjan算法学习笔记)
lhz2022
·
2025-01-21 22:22:45
·
算法·理论
主要是自学 + 看 bilibili 各位大佬的视频学的,有错误请见谅。
强连通
什么是强联通?
定义一个有向图 G ,如果对于任意两个点 u,v 都存在一条路径(双向都存在), 那么就是个强连通图。
特殊的,单个节点也算强连通图。
强连通分量
是一个图中极大 的强连通子图。(不是最大)
比如说这个有向图。节点 1 ,3 都是强连通分量。
那么节点 0,4,5 构成的那个子图显然也是强连通的,它是不是强连通分量呢?
不是。因为当我们把节点 2 放进来,发现也是强连通的。也就是说,图 G 的子图 G' 是强连通分量的条件是:
不存在一个 $G$ 的子图 $F$ 使得 $F$ 是强连通的且 $G'$ 是 $F$ 的真子图。
## 怎么求强连通分量?
用 Tarjan 算法即可。
至于 dfs 生成树,我觉得没有太大的必要讲。
```cpp
vector<int> g[N];//边
int dfn[N],low[N],stk[N],tp,tot,vis[N];//dfs序,从当前节点开始能够达到的dfs序最小的节点是多少,栈,用来计数dfs序的,是否在栈内
int n,m;
int bel[N];//该节点在哪个强连通分量内
```
```cpp
void tarjan(int x){
low[x]=dfn[x]=++tot;//初始化
stk[++tp]=x;//入栈
vis[x]=1;
for(auto v:d[x]){
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);//显然成立
}
else if(vis[v]){
low[x]=min(low[x],dfn[v]);//这里的v可能指向x的一个之前的节点(这是一条返祖边)
}
}
if(dfn[x]==low[x]){//是强连通分量dfs序最小的一个节点
++scc;
int y=stk[tp];
while(1){//根据dfs的性质,在此之后的这些节点都是在同一个强连通分量里面的。
int u=stk[tp--];
bel[u]=scc;
vis[u]=0;
if(u==x) break;
}
}
}
```
## DAG 上的 dp
先考虑一个比较简单的例子。对 P3387 进行简化。如果本题中的图是一个 DAG,怎么求?
我们设 $dp_i$ 代表到 $i$ 这个节点时可以取得的最大值,则对于每一条边 $[u,v]$ 都有 $dp_v=\max(dp_v,dp_u+val_v)$ 必然成立。
然而,如何以正确的顺序进行 dp 呢?可以对这个图进行拓扑排序,然后按拓扑序求解。
但是本题都带上了【模板】缩点 了,那么就必须将一下缩点。
## 缩点
我们发现在本题中不要求每个节点和边只经过一次,于是我们发现如果存在一个强连通分量,那么就可以得到这个强连通分量中所有点的权值。
这就启发我们把强连通分量抽象为一个节点。就哪之前的图举个例子:

变成这样

其中每个节点的权值就是之前强连通分量中的所有节点权值之和,这就是缩点。
容易证明,缩点后的图一定是一个 DAG,于是按照上述方法进行 dp 即可。
几个~~模板题~~练习:
#### 巨简单题 P2002
有 $n$ 个城市,中间有单向道路连接,消息会沿着道路扩散,现在给出 $n$ 个城市及其之间的道路,问至少需要在几个城市发布消息才能让这所有 $n$ 个城市都得到消息。
首先,如果有一个强连通分量,那么在该节点中任意一个节点放出消息则必定使整个分量收到,可以缩点。
缩点完成后直接统计入度为 $0$ 的点的数量即可。
P2835 也是同理,只是改了输入,~~题面变长~~。
#### 简单题 P2341
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢” 是可以传递的 —— 如果 $A$ 喜欢 $B$,$B$ 喜欢 $C$,那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。
先把喜欢关系建图。
首先如果图是强连通的,那么每个奶牛都可以当明星。
然后就是缩点,然后考虑所有出度为 $0$ 的点。如果只有一个,那么必然这个强连通分量中的奶牛都可当明星。
但是如果不止一个呢?那么就没有牛能当明星。
这些都是比较显然的。
#### 有点思维的 P2476
其实第一问就是上一题了。
主要是第二问:给你一个 DAG,求最少加上几条边即可使其变成强连通分量?
~~看了一下题解,~~设入度为 $0$ 的点集是 $P$, 出度为 $0$ 的点集是 $Q
当 |P|\leq|Q| 时
当 |P|=1 则有所有的点都可以从这一个点出发到达,那么只需把 Q 中每一个节点连到这个入度为 0 的点上,答案是 |Q| 。
当 |P|\geq 2 则必然 |Q|\geq|P|\geq2 ,则必有 4 个点 p_1,p_2,q_1,q_2 前两者是 P 中的,后两者是 Q 中的,且从 p_1 可以走到 q_1 ,从 p_2 走到 q_2 。此时,连接 q_1,p_2 。这时的新的 |Q'|=|Q|-1,|P'|=|P|-1 。直到 |P'|=1 变成上面的情况,答案是 |Q| 。
当 |P|\geq |Q| 同理。
所以答案是 \max(|P|,|Q|) 。
稍微有一点改变 P1262
由于外国间谍的大量渗入,国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据,则称 A 可以揭发 B。有些间谍收受贿赂,只要给他们一定数量的美元,他们就愿意交出手中掌握的全部情报。所以,如果我们能够收买一些间谍的话,我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍,他手中掌握的情报都将归我们所有,这样就有可能逮捕新的间谍,掌握新的情报。
我们的反间谍机关提供了一份资料,包括所有已知的受贿的间谍,以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 n 个间谍(n 不超过 3000 ),每个间谍分别用 1 到 3000 的整数来标识。
请根据这份资料,判断我们是否有可能控制全部的间谍,如果可以,求出我们所需要支付的最少资金。否则,输出不能被控制的一个间谍。
先吐槽一下题面,根本没有说明什么叫做控制间谍。根据题解的代码,我们才能推断出控制一个间谍的前提是被至少一个 人揭发。这样我们才能对于图进行缩点。
先判断无解的情况,即是否存在既不能被揭发也不能被贿赂的间谍。我们可以通过搜索查明一个间谍是否可以被控制。
然后我们可以证明,如果所有的间谍都可以被控制,我们应当选择缩点之后入度为 0 的所有间谍进行贿赂,这必然是最优的(用反证法可以证明)。
实际上此时这一题就做完了。但是我们发现 Tarjan 算法的实现过程中其实也是搜索。所以我们可以从每个可以贿赂的间谍的位置开始跑 Tarjan,大大的减小了码量。