连通图的割点、割边(桥)、块、缩点,有向图的强连通分量VIP免费

连通图的割点、割边(桥)、块、缩点，有向图的强连通分量 一、基本概念 无向图 割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。 块：没有割点的连通子图 割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。 缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。 求块跟求缩点非常相似，很容易搞混，但本质上完全不同。割点可以存在多个块中(假如存在 k个块中)，最终该点与其他点形成 k个块，对无割边的连通子图进行缩点后(假设为 k个)，新图便变为一棵 k个点由 k-1条割边连接成的树，倘若其中有一条边不是割边，则它必可与其他割边形成一个环，而能继续进行缩点。 有割点的图不一定有割边，如： 3是割点，分别与(1,2)和(4,5)形成两个无割点的块 有割边的图也不定有割点,如： w(1,2)为割边， 有向图 强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点 二、算法 无向图 借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。 dfn[i]表示 DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]]) 设 v,u之间有边w(v,u)，从 v->u： 如果 low[u]>=dfn[v],说明 v的儿子u不能通过其他边到达v的祖先，此时如果拿掉 v,则必定把 v的祖先和v的儿子u，及它的子孙分开，于是 v便是一个割点，v和它的子孙形成一个块。 如果 low[u]>dfn[v]时，则说明 u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果 v,u 之间有两条无向边，需要仍视为割边的话，则在 DFS 的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致 low[u]==dfn[v] ,而在另外一些问题中，比如电线连接两台设备 A,B 如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏 A 和B 之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS 时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id 号，在开始遍历 v->u 前检查它的id 是否在上一次 u->v时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边...