关于最小生成树,拓扑排序、强连通分量、割点、2-SAT的一点笔记

时间:2023-12-17 18:33:02

关于最小生成树,拓扑排序、强连通分量、割点、2-SAT的一点笔记

前言:近期在复习这些东西,就xjb写一点吧。当然以前也写过,但这次偏重不太一样

MST

最小瓶颈路:u到v最大权值最小的路径。在最小生成树上。是次小生成树的一个子问题qwq

最小极差生成树:枚举最小生成树上的最小权值的大小

topo sort

应用:

  1. 可以去掉基环树上的树
  2. DAG上拓扑序小的点指向拓扑序大的点。混合图变DAG时拓扑排序一下然后把无向边从左往右连就可以了。(无解:原来有向边构成的图不是DAG)

Tarjan

强连通分量 SCC

low[u]定义为u子树中的点通过back edge和cross edge能达到的时间戳最小的点v的时间戳,且满足v能到达u(即v不在其他已经确定的SCC中)

if(!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if(!belong[v]) low[u] = min(low[u], dfn[v]);

割点

low[u]定义不变,由于是无向图所以u和父亲的连边就是tree edge,即v不可以是父亲

然后要特判根的时候,至少俩孩子才可以

PS:删点变树,不能删割点

2-SAT

以前的

形式:

每个变量有两个取值(x,x'),有一些条件限制了某两个变量不能同时取某个值。即“或”。

构图:

对于限制(a,b),连有向边(a,b'),(b,a')

a -> b 意味着a成立时b必须成立

染色做法:

选择一个没有赋值的变量x,赋值为真,然后dfs染色下去,冲突则无解(x和x'都为真)

应用:

  1. 判断某个变量在该系统中是否可取真:

    从此变量开始dfs即可

  2. 求字典序最小的解:

从小到大,先赋值真染色,冲突的话把这次染色回滚掉,再赋值假染色

就是说进行x时,1...x-1时dfs染色的结果还保留着

复杂度:最坏\(O(nm)\)

优势在于我们拥有决定一个变量取值的能力

SCC做法

原图有对称性

显然一个scc中的点要么都选要么都不选,x和x'在同一个scc中则无解

缩点,反向连边

进行拓扑排序,选第一个未染色的点,染白色,然后将否定点及其新图后代dfs染黑色(注意边是反向的,所以一个点为假那么他的后代一定为假)。重复此过程。

复杂度:\(O(m)\)

局限性很强,只能判断是否有解和构造一组解

字典序最小的解也不可做,因为toposort中不断加入ind=0的新点,标号更小的点可以是后加入的(但这时这个点可能已经因为之前的煞笔操作而被染成黑色了)