在连通分量这一节中,主要包括:
无向图的割点和点双连通分量,桥和边双连通分量,有向图的强连通分量
其中,主要利用到的是两个数组:
low[u]:u以及他的后代所能回到的最小的dfn值.
dfn[u]:u点的访问时间.
无向图的割点和点双连通分量
割点定义: 如果删除一个点后,连通块数量增加,该点为割点.
判定条件: 如果一个点为割点,需要满足low[u]$\geq$dfn[v],而如果u为根节点需要满足他的儿子需要$child\geq$2.
代码: 割点
点双连通分量定义: 子图中任意两个点之间至少存在两条”点不重复“的路径.
判定条件:没写过
代码:没写过
无向图的桥和边双连通分量
桥的定义: 如果删除一条边后,连通块数量增加,该边为割边.
判定条件: v的后代只能连回v自己,既 $low[v]>dfn[u]$. 桥特别要注意重边,为了去重边,我们传边的编号.
代码: 桥
边双连通分量定义: 子图中任意两点之间至少存在两条”边不重复“的路径.
求解方法: 一个图中,把所有的桥去掉,每个连通分量对应着原图中的一个边双连通分量.
代码: 加最少的边,让整个图变成边双连通
hint
- 边双连通分量常伴随着缩点,然后得到一树,树上每个节点都是一个边双连通分量,树上的每条边都是桥.
有向图的强连通分量
强连通分量的定义: 一个强连通分量内,任意两个点之间互相可达.
判定条件: 如果$low[u]==dfn[u]$,那么u点为该强连通分量的”根”
代码: 加最少的边让有向图强连通 注意特判连通分量为1的情况
hint
- 对于一个有向图,我们都可以考虑一下缩点,因为缩点后是一棵有向树,对有向树操作,我们就可以很方便的求DAG上的最长路等等,树具有非常优美的性质,无向图也是同理.