綦江中国建设银行官网站,专业做二手网站,深圳 网站建设公,如何做网站淘客知识点
dfs树
对一个图运行 dfs 算法#xff0c;每个点uuu的父亲定义为第一次遍历uuu时的前驱结点#xff0c;若无则为根。 无向图的 dfs树 没有横叉边。 有向图的 dfs树 横叉边方向唯一#xff0c;总是从后访问的点指向先访问的点。 dfs树详解
tarjan
点双
定义#…知识点
dfs树
对一个图运行 dfs 算法每个点uuu的父亲定义为第一次遍历uuu时的前驱结点若无则为根。 无向图的 dfs树 没有横叉边。 有向图的 dfs树 横叉边方向唯一总是从后访问的点指向先访问的点。 dfs树详解
tarjan
点双
定义
不存在割点的图。
性质 两点一线型点双较为特殊以下在讨论特定性质时可能不纳入考虑范围。
点双的dfs树上根只有一个儿子除叶子和根外每个点都有回边跨过。 表述1点双两点一线型除外中任意两点至少包含在一个简单环内。 表述2点双两点一线型除外中任意两点间都存在至少两条简单路径并且这两条路径不经过相同的点。 表述3点双两点一线型除外中任意两条边至少包含在一个简单环内。对于点双中任意两点u,vu,vu,v若点ppp在点双中则一定存在u−p−vu-p-vu−p−v的简单路径若点ppp不在点双中则一定不存在u−p−vu-p-vu−p−v的简单路径。 对于点双中的任意一对点连接它们的简单路径所经过点的并集一定就是这个点双本身。对于点双中任意两点u,vu,vu,v若边ppp在点双中则一定存在u−p−vu-p-vu−p−v的简单路径。若点双中有奇环由3.4.得任意两点间的简单路径有偶数长度和奇数长度的所以点双里的所有边和点都在奇环上。一个有割点的无向图可以由若干个点双组成点双间以割点相连接两相邻的点双之间的公共点一定是唯一的且一定是割点。无向图中的每个割点至少属于两个点双其余点和每条边都只属于一个点双。点双连通分量一定是边双连通分量两点一线型除外反之不一定。
圆方树
圆方树是根据点双把无向图缩点所形成的树。 我们把每一个点双缩成一个 “方点”把原有的点称作 “圆点”。然后我们把原图的边全部删除让每个点向其所属的点双的 “方点” 连边。 显然一个割点会向多个方点连边而由此除了根节点以外所有的非割点都是叶子节点。 我们也知道圆点和圆点之间不会互相连边方点和方点之间也不会互相连边。 第一个是原图第三个是原图对应的圆方树
应用
处理有关简单路径的问题处理有关图的连通性的问题%%%大佬的Blog
边双
定义
不存在桥的图。
性质
边双的dfs树上每条树边都有回边跨过。 表述1边双中任意一条边都包含在至少一个简单环中。 表述2边双中任意两点间都存在至少两条简单路径并且这两条路径不经过相同的边。不是点双的边双可以由点双组成。 由两个点双组成的边双在一个有割边的无向图中把每一个边双缩成一个点然后这些点之间由原来的割边相连形成了一棵树。无向图中两点一线型点双的边其实就是割边割边不属于任何边双而其它非割边的边都属于且仅属于一个边双。
小小总结
点双和边双都是 由一些简单环组成的无向连通图 不严谨地说点双是边的集合边双是点的集合。 图上的简单路径问题一般用圆方树点双解决。
强连通分量
定义
若有向图GGG满足图中任意两点u,vu,vu,v间都存在从uuu到vvv的有向路径和从vvv到uuu的有向路径则称GGG是一个强连通图。有向图的极大强连通子图称为强连通分量。
性质
在强连通图中每个点的入度和出度一定都不为0。把有向图中的每个强连通分量缩成一个点将得到一个DAGDAGDAG(有向无环图)。
Kosaraju 算法
SAT 2-SAT
入门讲解 入门讲解
题目
POJ2942 Knights of the Round Table
题意判断每个点是否能在奇环内。
题解若点在一个奇环内则这个环一定在点所在的点双内而点双中只要存在一个奇环点双中的所有点都可以在奇环上。奇环的判断二分图染色后只要有一个点和它的相邻节点的颜色相同就找到了奇环。
Code
AGC038D Unique Path %%%zjr学长 摘自此Blog
XSY3273 graph
题意有一个无向图它没有重边和自环。现在有一些询问形如“u,vu,vu,v之间是否存在一条长度为奇数的简单路径” 这里简单路径定义为不经过重复的点的路径。
题解首先建出dfs树然后判断u,vu,vu,v间的树上路径长度是否为奇数 不是奇数的话考虑原图的圆方树因为任意两点间的简单路径都可以拆分成经过的点双所以就有以下结论 对于树上距离为偶数的u,vu,vu,v它们之间存在长度为奇数的简单路径当且仅当它们的树上路径经过了至少一条在奇环上的边 所以只需要求树上路径是否经过这样的边每找到一个奇环这个奇环所在的点双所包含的边都是满足要求的边tarjan预处理即可
Code
HDU2767 Proving Equivalences 如果这个图本身就是强连通的不用加任何边。 否则把每个强连通分量缩成一个点得到一个DAGDAGDAG。记in[i]in[i]in[i]为点iii的入度out[i]out[i]out[i]为点iii的出度那么DAGDAGDAG上的点可以分为以下四类
in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0in[i]0,out[i]0
贪心策略第3类点向第2,4类点连边第4类点再向第2类点连边 所以令DAGDAGDAG变为强连通加的最少边数为max(入度为0的点数,出度为0的点数)max(入度为0的点数,出度为0的点数)max(入度为0的点数,出度为0的点数)
POJ3177 Redundant Paths G 题解 把边双缩成点。 tarjantarjantarjan缩点后图变成树首先特判树中点数n≤2n\leq 2n≤2的情况。 考虑n2n2n2的情况答案为⌊cntleaf12⌋\lfloor\frac{cnt_{leaf}1}{2}\rfloor⌊2cntleaf1⌋。 构造具体方案时以任意度大于111的点为根只需要保证任意两个叶子连边后与根成环 当奇数个叶子时可以将一个叶子与根相连又转换成了偶数叶子情况。
具体构造 tarjantarjantarjan缩点后图变成树选择度数大于111的点为根按照dfsdfsdfs序存下所有叶子leaf[i]leaf[i]leaf[i]表示按dfsdfsdfs序排序后的第iii个叶子共ggg个叶子。 将leaf[i]leaf[i]leaf[i]与leaf[i⌊g2⌋]leaf[i\lfloor\frac{g}{2}\rfloor]leaf[i⌊2g⌋]连边(i≤⌊g12⌋i\leq \lfloor\frac{g1}{2}\rfloori≤⌊2g1⌋)。
构造方法证明 见2020牛客多校第三场C
CF1000E We Need More Bosses “必须经过的边”就是sss到ttt路径上的割边把无向图中的边双缩成点得到一棵树求树的直径即可。
Code
CF1137C Museums Tour d≤50d\leq 50d≤50 摘自此Blog
Code
CF1220E Tourism 在边双内走一定能回到原点故把边双缩成点。
然后就是树形DP f[cur]f[cur]f[cur]代表走到curcurcur子树还能回的贡献g[cur]g[cur]g[cur]代表走到curcurcur子树回不来的贡献题目所求即为g[s]g[s]g[s]。
先考虑fff的转移 如果子节点能回来f[cur]f[to]f[cur]f[to]f[cur]f[to] 然后g[cur]max(g[to])f[cur]g[cur] max(g[to]) f[cur]g[cur]max(g[to])f[cur]走完所有可以返回的儿子再找个最大的不能返回的
这样有一个问题如果f[cur]g[cur]f[cur]g[cur]f[cur]g[cur]结点curcurcur是否要返回 于是再g[cur]max(g[cur],f[cur]−f[to]g[to])g[cur] max(g[cur], f[cur] - f[to] g[to])g[cur]max(g[cur],f[cur]−f[to]g[to]) 摘自此Blog
Code
CF732F Tourist Reform Blog
Code
POJ3694 Network
题意在线查询一个无向图加入一条边后减少了多少条桥。 题解先将所有的边双缩点得到一颗树。初始时桥数即为树的边数树边边权皆为1。 每次询问加入边(x,y)(x,y)(x,y)设c[i]c[i]c[i]表示点iii所在边双。 若c[x]c[y]c[x]c[y]c[x]c[y]无影响。 否则减去的桥数为树上c[x]c[x]c[x]到c[y]c[y]c[y]的路径上边权的和然后把该路径上树边的边权全部改为0。
[HNOI2012]矿场搭建 摘自此Blog
