关于最小生成树,拓扑排序、强连通分量、割点、2-SAT的一点笔记
前言:近期在复习这些东西,就xjb写一点吧。当然以前也写过,但这次偏重不太一样
MST
最小瓶颈路:u到v最大权值最小的路径。在最小生成树上。是次小生成树的一个子问题qwq
最小极差生成树:枚举最小生成树上的最小权值的大小
topo sort
应用:
- 可以去掉基环树上的树
- 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'都为真)
应用:
-
判断某个变量在该系统中是否可取真:
从此变量开始dfs即可
求字典序最小的解:
从小到大,先赋值真染色,冲突的话把这次染色回滚掉,再赋值假染色
就是说进行x时,1...x-1时dfs染色的结果还保留着
复杂度:最坏\(O(nm)\)
优势在于我们拥有决定一个变量取值的能力
SCC做法
原图有对称性
显然一个scc中的点要么都选要么都不选,x和x'在同一个scc中则无解
缩点,反向连边
进行拓扑排序,选第一个未染色的点,染白色,然后将否定点及其新图后代dfs染黑色(注意边是反向的,所以一个点为假那么他的后代一定为假)。重复此过程。
复杂度:\(O(m)\)
局限性很强,只能判断是否有解和构造一组解
字典序最小的解也不可做,因为toposort中不断加入ind=0的新点,标号更小的点可以是后加入的(但这时这个点可能已经因为之前的煞笔操作而被染成黑色了)