不知道先复习什么了,那就先来问候一下$Tarjan$一家吧$QwQ$

部分内容$Ctrl-C$于网络$QAQ$

有向图的强连通分量

强连通分量,简称强分支,$SCC$。

有向图中,尽可能多的若干顶点组成的子图中,

所有顶点都是互相可到达的,则这些顶点成为一个强连通分量。

基本思想

①一种基于$DFS$的算法,时间复杂度线性,为$O(n+m)$

②$DFS$到某个点时,如果该点有一条边指向已访问过的且不属于别的强分支的点,

​ 则说明有环路,这个环路上的点都属于一个强连通分量。

准备工作

①$DFN$数组,时间戳。代表$DFS$到该点的时间(次序)。

②$low$数组,追溯值。

​ 代表通过该点自己,或者该点搜索子树中某个节点,可以回溯到的最早时间戳。

​ 如果没有这样的边,则该点$low$值等于$dfn$。

③栈,用于记录在一个连通分支中的点。

算法过程

①当$x$第一次被访问到时,令$dfn[x]=low[x]=++t$并入栈。

②遍历$x$的所有儿子$y$。

​ 若$y$未被访问过,则递归处理$y$,$y$处理完后,令$low[x]=min(low[x],low[y])$

​ 若$y$已访问过,且还在栈里,则令$low[x]=min(low[x],dfn[y])$。

③儿子处理结束后,若$dfn[x]=low[x]$,则退栈直到$x$出栈的元素都是一个强分支的元素。

int t;//时间戳变量
int cnt;//强连通分量数量
int belong[maxn];//某个点属于哪个强分支 
int dfn[maxn],low[maxn];//时间戳,回溯值
stack<int> s//栈 
int insack[maxn]//记录结点是否在栈中的标记数组 
int Tarjan(int u){
    dfn[u]=low[u]=++t;
    instack[u]=1;
    s.push(u); 
    for(int i=first[u];i;i=line[i].nextt){
        int v=line[i].to;
        if(dfn[v]==0){//如果v没有被访问过 
            Tatjan(v);
            low[u]=min(low[u],low[v]);
            //儿子v处理完,更新u的low值 
        } 
        else if(instack[v]){//v已经访问过了,且在栈中 
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){//强连通分量判定条件 
        cnt++;
        do{ 
            int xx=s.top();
            instack[xx]=0;
            belong[xx]=cnt;
            s.pop();
        }while(u!=xx);
    }
} 

无向图的割点

在一个无向图中,如果去掉一个点和它所连出去的的所有边,

使得剩下的点不联通,则这个点被称为割点。

基本思想

①对于根节点,如果其子树的数量大于1,则其一定为割点。

②对于非根结点,如果它的子树中最早能访问到的结点都比它后访问,则其一定为割点。

​ 及子树能达到的$DFN$最小的结点的时间>=自己的时间。

​ 即$dfn[u]<=low[v]$时,$u$一定为割点。

void tarjan(int u){
    dfn[u]=low[u]=++t;
    int cnt=0;//统计根节点子树数量
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!dfn[v]){
            cnt++;
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(u==root&&cnt>1) cutpoint[u]=1;
            //如果是更结点且子树数量大于1,为割点。
            if(u!=root&&dfn[u]<=low[v]) cutpoint[u]=1;
            //如果是非根结点且子树能达到的DFN最小的结点的时间>=自己的时间,为割点。
        }
        else low[u]=min(low[u],dfn[v]);
    }
} 

无向图的点双联通分量

若一张无向图不存在割点,则称它为点双联通图。

无向图的“极大点双连通子图”称为“点双连通分量”,简记为$v-BCC$。

基本思想

①不同的点双联通分量之间最多只有一个公共点,且一定是割点。

②任意一个割点,都至少是两个点双联通分量的公共点。

一旦找到一个割点,则由该割点出发的点双连通分量,一定在该点作为根的$DFS$树中。

所以,每发现一个割点,就把子树出栈,加上割点自己,构成一个$v-BCC$。

注意:割点可能属于多个$v-DCC$。

实现方法

为了求出“点双连通分量”,需要在$Tarjan$算法的过程中维护一个栈,并按如下方式维护栈中元素:
①当一个节点第一次被访问时,把该节点入栈。
②当割点判定法则中的条件$dfn[x]<=low[y]$成立时,无论$u$是否为根,都需要:
Ⅰ从栈顶不断弹出节点,直至节点$v$被弹出。
Ⅱ刚才弹出的所有节点与节点x一起构成一个$v-BCC$。

void tarjan(int u){
    dfn[u]=low[u]=++t;
    s.push(u);
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(dfn[v]==0){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                cutblock++;
                do{
                    int xx=s.top();
                    block[cntblock].push_back(xx);
                    s.pop();
                }while(v!=xx);
                blok[cntblock].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
} 

无向图的割边

在一个无向图中,如果去掉一条边,

使得剩下的点不联通(即分成一个以上的强连通分量)时,这条边被称为割边。

基本思想

①桥一定是搜索树中的边,并且一个简单环中的边一定都不是桥。

②无向边$(u, v)$是桥,当且仅当搜索树上存在$u$的一个子节点$y$,满足:$dfn[u] < low[v]$。

根据定义,$dfn[u] <low[v]$说明从$v$出发,在不经过$(u,v)$的前提下,不管走哪条边,都无法到达$u$或比$u$更早访问的节点。

若把$(u, v)$删除,则$v$与节点$u$没有边相连,图断成了两部分,所以此时$(u, v)$为桥。

反之,若不存在这样的子节点$u$和$v$,使得$dfn[u] < low[v]$,说明$v$能绕行其他边到$u$或比$u$更早的节点,$(u, v)$也就不是桥。

注意

需要注意的是, 因为我们要遍历的是无向图, 所以从每个节点$x$出发,总能访问到他的父节点$fa$。

根据$low$的计算方法,$(x, fa)$属于搜索树上的边,且$fa$不是$x$的子节点,故不能用$fa$的时间戳来更新$low[x]$。

如果仅记录每个节点的父节点,会无法处理重边的情况:

——当$x$与$fa$之间有多条边时,$(x, fa)$一定不是桥,

但在这些重复计算中,只有一条边在搜索树上,其他的几条都不算,

故有重边时,$dfn[fa]$可以用来更新$low[x]$,但上述做法办不到。

解决方案是:

记录“递归进入每个节点的边的编号”。

编号可认为是边在邻接表中储存下标位置。

把无向图的每条边看做双向边,成对存储在下标“$2和3$”,“$4和5$”,“$6和7$”处。

若沿着编号$i$的边递归进入节点$x$,则忽略从$x$出发的编号为$i\ xor\ 1$的边,通过其他边计算$low[x]$即可。

补充

对于非负整数$n$

当$n$为偶数时,$n\ xor\ 1$等于$n+1$

当$n$为奇数时,$n\ xor\ 1$等于$n-1$

因此$“0与1”$$“2与3”$$“3与5”……$关于$xor\ 1$运算构成了成对变换

这一性质经常用于图论邻接表中边集的存储。

在具有无向边(双向边)的图中把一对正反方向的边分别储存在邻接表数组的第$n$与$n+1$个位置(其中$n$为偶数),就可以通过$xor\ 1$运算获得与当前边$(x, y)$反向的边$(y, x)$的存储位置。

void tarjan(int u,int from){
    dfn[u]=low[u]=++t;
    for(int i=first[u];i;i=line[i].nextt){
        if(i==(from^1)) continue;
        int v=line[i].to;
        if(dfn[v]==0){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]){
                cntbridge++;
                bridge[i]=1;
                bridge[i^1]=1;
            }
        } 
        else low[u]=min(low[u],dfn[v]);
    }
}

无向图的边双联通分量

若一张无向图不存在割边,则称它为边双联通图。

无向图的“极大边双连通子图”称为“边双连通分量”,简记为$e-BCC$。

基本思想

求出无向图中所有的桥,将桥删除后,图会分成若干块,每一个连通块都是一个“边双连通分量”。

实现方法

①先用$Tarjan$算法标记出所有的桥。

②对整个无向图执行一次深度优先遍历(不访问割边),划分出每个连通块。

int e-vcc;//记录边双联通分量数量
int belong[maxn];//记录每个节点属于哪个边双联通分量
void dfs(int x){
    belong[x]=e-vcc;
    for(int i=first[x];i;i=line[i].nextt){
        if(bridge[i]==1) continue;
        int y=g[x][i];
        if(belong[y]==0) dfs(y);
    }
}
//main
for(int i=1;i<=n;i++){
    if(belong[i]==0){
        dfs(i);
    }
} 

撒花★,°:.☆( ̄▽ ̄)/$:.°★