dfs树与tarjan算法

📒 关于 dfs 树的笔记、用 tarjan 求割点、割边、双连通分量、强连通分量、缩点……

边的分类

对于有向图

树边、前向边、后向边（返祖边）、横叉边

树边dfs 形成的边
前向边指向子孙方向的边
后向边（返祖边） 指向祖先方向的边
横叉边指向另一子树的边

对于无向图

树边，后向边（返祖边），前向边

树边dfs 形成的边
后向边（返祖边） 指向祖先方向的边

---

无向图的双连通分量

双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用 Tarjan 算法。 ————百度百科

其中边双连通分量一定是点双连通分量，而点双连通分量不一定是边双连通分量（反例：两点一边）

割点

对于一个无向联通图，去掉一个点，这个图不联通，则该点为割点，下图中 u，v 即为割点

做法

（后文会用到）考虑对图进行 dfs，记录时间戳$dfn[u]$,还有$low[u]$表示$u$点通过返祖边能回到的最远的父亲。

如果当前$（u \to v）$访问到树边则显然$low[u]=min(low[u],low[v])$,若当前访问到的是返祖边，则$low[u]=min(low[u],dfn[v])$。判断树边和非树边只要看看$dfn$是否等于零就行了。
如何判断割点？假如$low[v]>=dfn[u]$是不是就可以判断点$u$是割点，因为点$v$能到达的最远的父亲在$u$之下，那么删去$u$，$v$子树就没有连着上面的边了（无向图中无）。但是，注意跟节点例外，反例就是根节点只要一个孩子。
所有对于任意非根节点，找到一个孩子使$low[v]>=dfn[u]$，即为割点，对于根节点，只要有不小于两个孩子就是割点

code

void dfs(int u,int f) {
    dfn[u]=low[u]=++num;
    int child=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=pnt[i];
        if(!dfn[v]) {
            child++;
            dfs(v,u);
            low[u]=min(low[u],low[v]);//对于割点不用判断重边，因为两点多条边和一条边是一样的
            if((u==root&&child>1)||(u!=root&&dfn[u]<=low[v])) {
                //u是割点
            }
        }
        else if(v!=f) {
            low[u]=min(low[u],dfn[v]);
        }
    }
}

割边（桥）

对于一个无向联通图，去掉一条边，这个图不联通，则该点为割边（桥），上图中 x 即为桥

做法

若边$u \to v$是桥，当且仅当$u \to v$是树边，且满足$dfn[u]<low[v]$，因为 v 想到达 u 必须经过边$u \to v$，删除这条边，图就不连通了。
注意：实现时要考虑重边的问题，故要标记边而不是标记点，边在标记时把反向边（^1)标记了。

code

void dfs(int u) {
    dfn[u]=low[u]=++num;
    int child=0;
    for(int i=head[u];i;i=nxt[i]) {
        if(vis[i]) continue;
        vis[i]=vis[i^1]=true; //标记边与反向边
        int v=pnt[i];
        if(!dfn[v]) {
            dfs(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]) {
                //i是割边
            }
        }
        else {
            low[u]=min(low[u],dfn[v]);
        }
    }
}

求点双连通分量

😅 未完待续。。。