蒟蒻lhz2022的图论(tarjan算法学习笔记)

· · 算法·理论

主要是自学 + 看 bilibili 各位大佬的视频学的,有错误请见谅。

强连通

什么是强联通?

定义一个有向图 G,如果对于任意两个点 u,v 都存在一条路径(双向都存在), 那么就是个强连通图。

特殊的,单个节点也算强连通图。

强连通分量

是一个图中极大的强连通子图。(不是最大)

比如说这个有向图。节点 13 都是强连通分量。

那么节点 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 呢?可以对这个图进行拓扑排序,然后按拓扑序求解。 但是本题都带上了【模板】缩点 了,那么就必须将一下缩点。 ## 缩点 我们发现在本题中不要求每个节点和边只经过一次,于是我们发现如果存在一个强连通分量,那么就可以得到这个强连通分量中所有点的权值。 这就启发我们把强连通分量抽象为一个节点。就哪之前的图举个例子: ![](https://cdn.luogu.com.cn/upload/image_hosting/k0hx2rek.png) 变成这样 ![](https://cdn.luogu.com.cn/upload/image_hosting/9x984o4p.png) 其中每个节点的权值就是之前强连通分量中的所有节点权值之和,这就是缩点。 容易证明,缩点后的图一定是一个 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),每个间谍分别用 13000 的整数来标识。

请根据这份资料,判断我们是否有可能控制全部的间谍,如果可以,求出我们所需要支付的最少资金。否则,输出不能被控制的一个间谍。

先吐槽一下题面,根本没有说明什么叫做控制间谍。根据题解的代码,我们才能推断出控制一个间谍的前提是被至少一个人揭发。这样我们才能对于图进行缩点。

先判断无解的情况,即是否存在既不能被揭发也不能被贿赂的间谍。我们可以通过搜索查明一个间谍是否可以被控制。

然后我们可以证明,如果所有的间谍都可以被控制,我们应当选择缩点之后入度为 0 的所有间谍进行贿赂,这必然是最优的(用反证法可以证明)。

实际上此时这一题就做完了。但是我们发现 Tarjan 算法的实现过程中其实也是搜索。所以我们可以从每个可以贿赂的间谍的位置开始跑 Tarjan,大大的减小了码量。