0x66 Tarjan算法与无向图连通性(1)

……是什么?

  给定无向连通图G=(V,E)(不一定连通);

  割点:若对于x∈V,从图中删去节点x以及所有与x关联的边后,G分裂成两个或两个以上不相连的子图,则称x为G的割点。

  桥(割边):若对于e∈E,从图中删去边e之后,G分裂成两个不相连的子图,则称e为G的桥或割边。

  (如果图不连通,“割点”和“桥”就是它的各个连通块的“割点”和“桥”)。

  时间戳:在图的深度优先遍历过程中,按照每个节点第一次被访问的时间顺序,以此给予N个节点1~N的整数标记,该标记就被称为“时间戳”,记为dfn[x]。

  搜索树:在无向联通图中任选一个节点出发进行深度优先遍历,每个点只访问一次。所有发生递归的边(x,y)构成一棵树,我们把它成为“无向联通图的搜索树”。

  (严谨的,从x到y是对y的第一次访问)

  搜索森林:无向图的各个连通块的搜索树构成无向图的“搜索森林”。

  追溯值: 设subtree(x)表示搜索树中以x为根的子树,“追溯值”low[x]定义为以下节点的时间戳的最小值:

    1.subtree(x)中的节点。

    2.通过1条不在搜索树上的边,能够到达subtree(x)的节点。

  割边判定法则:无向边(x,y)是桥,当且仅当搜索树上存在x的一个子节点y,满足:

    dfn[x]<low[y];

  割点判定法则:若x不是搜索树的根节点(深度优先遍历的起点),则x是割点当且仅当搜索树上存在x的一个子节点y,满足:

    dfn[x]<=low[y];

……为什么?

  割边判定法则:根据定义,dfn[x]<low[y]说明从subtree(y)出发,在不经过(x,y)的前提下,不管走哪条边,都无法到达x或比x更早访问的节点。若把(x,y)删除,则subtree(y)就好像形成了一个封闭的环境,与节点x没有边相连,图断开成了两部分,因此(x,y)是割边。反之,若不存在这样的子节点y,使得dfn[x]<low[y],则说明每个subtree(y)都能绕行其他边到达x或比x更早访问的节点,(x,y)自然就不是割边。

  割点判定法则与之类似。

……怎么做?

  追溯值:为了计算low[x],应该先令low[x]=dfn[x],然后考虑从x出发的每条边(x,y):

    若在搜索树上x是y的父节点,则令low[x]=min(low[x],low[y]);

    若无向边(x,y)不是搜索树上的边,则令low[x]=min(low[x],dfn[y]).  

  

上一篇:【2019北京集训2】duck 线段树优化建图+tarjan


下一篇:强连通分量(Tarjan)