tarjan算法求SCC，e-DCC，v-DCC

在介绍算法之前先引入几个概念：

时间戳： 在深度优先搜索时，每个点$x$第一次被访问的顺序为时间戳，记作$dfn[x]$（从$1$开始）

追溯值： 从$x$开始走，所能遍历到的最小时间戳，记作$low[x]$

$1.\text{tarjan}$求$\text{SCC}$

给定一张有向图$G$，$\forall u,v$，即存在从$u$到$v$的路径又存在从$v$到$u$的路径，那么该图$G$是强连通图。

强连通分量$\text{(SCC)}$ 就是有向图的极大强连通子图

为了方便，我们定义有向图中的四种边：

$(1)$ 树枝边：搜索树中的边

$(2)$ 前向边：搜索树中$x$是$y$的祖先节点

$(3)$ 后向边：搜索树中$y$是$x$的祖先节点

$(4)$ 横叉边：以上三种情况之外的边：$x$到$y$的边，并且满足$dfn[y]<dfn[x]$

一定是往左边连的边，如果往右，那么根据深度优先遍历会走到右边。

其中后向边和横叉边是构成环的重要的边，所以为了找到这两条边，$\text{tarjan}$算法在深度优先搜索时维护一个栈来记录节点$x$的祖先节点。如果正在访问的点恰好是栈中的祖先节点，那么就可以形成环，如果正在访问的点可以到栈中的祖先节点，那么他们三个以及搜索路径就可以构成环。

$\text{tarjan}$算法的步骤：

记全局时间戳为$timestamp$

$(1)$ 当$x$第一次被遍历时，将$x$入栈，初始化$dfn[x]=low[x]=++timestamp$

$(2)$ 遍历$x$的出边$j$：

$①$：若$j$未被访问$(dfn[j]=0)$，那就访问$j$，回溯之后更新追溯值$low[x]=\min (low[x],dfn[j])$

$②$：若$j$被访问过且$j$在栈中，更新追溯值$low[x]=\min (low[x],dfn[j])$

$(3)$ 从$x$回溯之前，判断是否$low[x]=dfn[x]$，如果有那么说明是环，则不断将栈中节点出栈，直到$x$出栈为止。

$\text{SCC}$的判定：

如果$x$是强连通分量的最高点，等价于$low[x]=dfn[x]$，那么就说明找到了整个强连通分量，则栈中从$x$到栈顶的所有节点构成强连通分量。

$\text{SCC}$缩点：

重新建图的时候只需要判定$id[i]$是否等于$id[j]$，
如果不相同就建新边。

代码：

void tarjan(int x) {
   
    dfn[x] = low[x] = ++ timestamp;
    s.push(x), st[x] = 1;
    for (int i = h[x]; ~i; i = ne[i]) {
   
        int j = e[i];
        if (!dfn[j]) {
   
            tarjan(j);
            low[x] = min(low[x], low[j]);
        } else if (st[j]) {
   
            low[x] = min(low[x], dfn[j]);
        }
    }
    if (dfn[x] == low[x]) {
   
        scc_cnt ++;
        int y;
        do {
   
            y = s.top();
            s.pop();
            st[y] = 0;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        } while (y != x);
    }
}

$scccnt$表示图中强连通分量的个数，$id[i]$数组表示$x$节点属于编号为$i$的强连通分量，$Size[i]$数组表示编号为$i$的强连通分量里点的个数。

$2.\text{tarjan}$求$\text{e-DCC}$

给定一张无向图$G$，如果不存在割边，则称为边双连通图，无向图的极大边双连通分量被称为边双连通分量$(\text{e-DCC})$

求割边：

找到一个条边，满足$dfn[x]<low[y](y是x子节点)$
因为从$y$出发，无论走到哪条边，都不可能到达$\ge dfn[x]$的点，所以删除这条边之后就将图分成了两部分。在算法中，可以巧妙地运用异或运算来标记割边。

$\text{e-DCC}$的判定：

只需要求出无向图中的所有割边，把割边删除，无向图会分成若干连通块，每一个连通块就是一个边双连通分量。

$\text{e-DCC}$缩点：

把每个$\text{e-DCC}$看成点，每条割边看成新边。

代码：

void tarjan(int x, int fa) {
   
    dfn[x] = low[x] = ++ timestamp;
    s.push(x);
    for (int i = h[x]; ~i; i = ne[i]) {
   
        int j = e[i];
        if (!dfn[j]) {
   
            tarjan(j, i);
            low[x] = min(low[x], low[j]);
            if (dfn[x] < low[j]) {
   
                st[i] = st[i ^ 1] = 1;
            }
        } else if (i != (fa ^ 1)) {
   
            low[x] = min(low[x], dfn[j]);
        }
    }
    if (low[x] == dfn[x]) {
   
        dcc_cnt ++;
        int y;
        do {
   
            y = s.top();
            s.pop();
            id[y] = dcc_cnt;
        } while (y != x);
    }
}

$id[i]$表示点$y$属于编号为i的双连通分量，$st[i],st[i\wedge 1]$标记每条割边，$dcccnt$表示边双连通分量的个数。

$3.\text{tarjan}$求$\text{v-DCC}$

给定一张无向图$G$，如果不存在割点，则称为点双连通图，无向图的极大点双连通分量被称为<stron>$(\text{v-DCC})$</stron>

求割点：

如果$x$不是搜索树的根节点，则$x$是割点当且仅当搜索树上存在一个子节点$y$使得$dfn[x]\le low[y]$

$\text{v-DCC}$的判定：

特判孤立点为单独的点双连通分量，除此之外，其他的点双连通分量大小至少为$2$。
做法：
$(1)$ 当节点第一次被访问，将节点入栈。
$(2)$ 当点$x$，出边$y$满足$dfn[x]\le low[y]$， 从栈顶不断弹出节点，直到$y$被弹出，那么所有弹出的节点与点$x$构成一个点双连通分量。

$\text{v-DCC}$缩点：

由于一个割点可能属于多个$\text{v-DCC}$，所以建图时必须将割点单独拿出来建，即每个割点向该割点所在的$\text{v-DCC}$连一条新边。设无向图$G$有$p$个割点和$t$个$\text{v-DCC}$，那么新图的节点个数为$p+t$

代码：

void tarjan(int x) {
   
    dfn[x] = low[x] = ++ timestamp;
    s.push(x);
    if (x == root && h[x] == -1) {
   
        dcc_cnt ++;
        dcc[dcc_cnt].push_back(x);
        return ;
    }
    int cnt = 0;
    for (int i = h[x]; ~i; i = ne[i]) {
   
        int j = e[i];
        if (!dfn[j]) {
   
            tarjan(j);
            low[x] = min(low[x], low[j]);
            if (dfn[x] <= low[j]) {
   
                cnt ++;
                if (x != root || cnt > 1) st[x] = 1;
                dcc_cnt ++;
                int y;
                do {
   
                    y = s.top();
                    s.pop();
                    dcc[dcc_cnt].push_back(y);
                } while (y != j);
                dcc[dcc_cnt].push_back(x);
            } 
        } else {
   
            low[x] = min(low[x], dfn[j]);
        }
    }
}

$dcccnt$表示点双连通分量的个数，$dcc[i][j]$数组表示新图中割点编号为$i$，对应$\text{v-DCC}$中编号为$j$的邻接矩阵。