$$Tarjan算法与无向图连通性$$

$无向图的割点与桥$

$给定无向图G = (V,E)$

$若对于v\in V,从图中删去v节点以及 x 关联的边,G分成了两个部分,这样的点v被称为割点$

$若对于e\in E,从图中删去边e,G分成了两个部分,这样的边e被称为桥或割边$

$时间戳$

$在图的深度优先遍历过程中,按照每个节点第一次被访问的时间顺序$

$依次给予N个节点1\sim N的整数标记,该标记被称为时间戳,记为dfn[x]$

$搜索树$

$在无向图连通性任选一个节点出发做深度优先搜索,每一节点只访问一次$

$产生地柜的边(x,y)构成了一棵树,这棵树被称为无向图的搜索树$

$追溯值$

$除了时间戳以外,Tarjan还引入了追溯值low[x]$

$设subtree(x)表示搜索树中节点x的子树,low[x]定义为以下节点的时间戳最小值：$

$1.subtree[x]中的节点$

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

$割边的判定法则$

$若无向边(x,y)是桥,且y是节点x的一个子节点,满足：$

$$dfn[x] < low[y]$$

$根据定义,dfn[x] < low[y]说明从subtree(y)出发$

$在不经过(x,y)的前提下,不管走哪条边,都无法到达x或比x更早的节点$

$因此,若把边(x,y)删除,subtree(y)形成了一个封闭的空间, (x,y)是桥$

$Code$

void tarjan(int x, int from)
{
    dfn[x] = low[x] = ++ times;
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y])
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (from ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
}

$割点判定法则$

$若x不是搜索树的根节点,只要x存在一个子节点y,满足：$

$$dfn[x] \leq low[y]$$

$若x是根节点,就要存在两个节点y_1, y_2, 满足上述条件$

$Code$

void tarjan(int x, int from)
{
    dfn[x] = low[x] = ++ times;

    int flag = 0;
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y])
            {
                flag ++ ;
                if (x != root || flag > 1)cut[x] = true;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}