图的连通性
这个专题,不太好说,因为涉及到的东西实在是太广泛太杂了,我们这里就只讲建模,至于建模之后的处理方式可以移步至其他的知识点。
强连通
对于有向图,我们可以发现,如果每个点的贡献和影响与这个点可达的点有关,那么我们就可以将一个强连通分量缩点,将原图转化为一个有向无环图,然后就可以套用 \(DAG\) 上的技巧进行处理。
然后就是,我们发现我们将这一个个强连通分量找出来的顺序恰好就是拓扑序的逆序,所以我们根本不需要建边,只需要根据需求正着或者倒着扫一遍即可。
点双联通
点双连通,一般来说都会有明显的提示,比如两个点路径的必经之点,又或者直接很明显的问你关于割点的问题。
求点双的方式和强连通类似,只不过,求点双是在遍历儿子的循环内部的,需要注意以下求割点的话要特判根,但是求点双不需要。
另外,两个点一条边的点双也是点双,这个玩意儿很容易弄错,这是点双中的骗徒,因为其他的点双都可以保证简单环,就双点点双这玩意儿,根本没有环!
顺带,说一下圆方树。
新建一些虚拟节点,称为方点,对于每一个点双都将点双内的所有点向方点连边,然后点双内部所有点互相的边断掉。
可以发现,任何两个点的路径一定是原点和方点交错出现的。
其次,任意两个点之间在原图上的必经点,就是他们在园方树上经过的所有圆点。
(这不比\(DFS\) 生成树好用多了)
边双联通
对于关于路径上必经边的题目,可以通过边双缩点,转化为一颗树,然后对树上问题进行处理。
另外就是,双连通没有横插边这种说法,所以可以放心大胆的丢掉 \(instack\) 这种东西。
小Trick
-
关于\(Tarjan\)基本原理
正确性是怎么得到保证的呢,其实说白了就是用了这两条性质
- 若\(A\) 和 \(B\) 强连通,\(B\) 和 \(C\) 强连通,那么\(A\) 和 \(C\) 也强连通。
- 在\(DFS\) 树上,只要是被遍历了,就一定说明祖先到他的路径上的所有点都可以到达他,所以返祖边保证了和祖先的强连通,而\(low\) 数组相当于找的这个强连通分量目前的代言人。
就这么简单,双连通的证明类似。
-
基于\(low\) 数组的\(Tarjan\) 扩展运用
我们发现,我们同一个强连通分量里的点的\(low\) 值不一定相同,只是因为访问的先后顺序导致的。
但是如果我们每次都先访问返祖边,然后再通过树枝边向下搜索,那么最后得到的\(low\) 数组对于同一个强连通分量一定是相同的,证明显然。
-
点双联通分量里的边
众所周知,强连通和边双都非常好处理联通分量里的边,唯独点双这个玩意儿,因为一个点可能会存在于多个点双之中,而且还有可能一个点双里面的几个点对于全局来说都是割点的情况,所以说在算法外找边是非常麻烦的。
所以我们可以直接在算法内解决,将记录点的栈改为记录边的栈即可,然后要注意,对于"返祖"的情况一定要认清楚究竟是返祖还是遍历了已遍历的子孙,记得特判这个。(找环的话要特别注意双点点双)