复习知识点 Tarjan

Tarjan算法与无向图联通性

无向图的割点与桥

给定无向连通图$G=(V,E)$:
割点:对于$x\in V$,从图中删去节点x以及所有与x关联的边之后，G分裂成两个或两个以上不相连的子图，则称x是G的割点。
桥(割边):若对于$e\in E$,从图中删去边e之后，G分裂成两个不相连的子图，则称e为G的桥。

Tarjan算法的一系列定义

时间戳
深度优先遍历的顺序，即dfs序.
记为dfn[x] (时间戳)
搜索树
在图G中任选一个节点出发进行dfs,每个点只访问一次。
所有发生递归的边构成一棵树.
追溯值
Tarjan算法引入了一个追溯值low[x]。
设subtree(x)表示搜索树中以x为根的子树。
low[x]定义为以下节点的时间戳的最小值：
1.subtree(x)中的节点
2.通过一条不在搜索树上的边，能够到达Subtree(x)的节点。

计算low[x]：
根据定义，先令low[x] = dfn[x]，然后考虑从x出发的每条边(x,y)
1.若在搜索树上x是y的父节点,则令low[x] = min(low[x],low[y])
2.若无向边(x,y)不是搜索树上的边,则令low[x] = min(low[x],dfn[y])

割边判定法

对于一条边(x,y)要想他是桥,当且仅当搜索树上x的一个子节点y，满足:

$$dfn[x] < low[y]$$
但由于是无向图，从每个点x出发，总会访问到他的父节点fa.
根据low的计算方法，(x,fa)属于搜索树上的边，且fa不是x的子节点,故不能用fa的时间戳来更新low[x]。
对于重边的情况,当x与fa之间有多条边时，(x,fa)一定不是桥。
故有重边时,dfn[fa]能更新low[x]

CODE:

void dfs(int now , int in_edge) {
    for(int i = head[now];i;i = Map[i].nex) {
        int v = Map[i].v;
        if(!dfn[v]) {
            dfs(v , i);
            low[now] = min(low[now] , low[v]);
            if(dfn[now] < low[v]) bridge[i] = true;
        }else {
            if(i != (in_edge ^ 1)) low[now] = min(low[now] , dfn[v]);
        }
    }
    return;
}