Tarjan与图连通性

有向图强连通分量

简介

强连通分量定义: 在有向图 $G$ 中，任意两个节点可以互相到达。

强连通分量（SCC）定义: 极大的强连通子图。

Tarjan 算法

我们先要学习一下 DFS 生成树：

有向图的 DFS 生成树主要有四种边：树边，返祖边，横叉边，前向边。

考虑 DFS 生成树与强连通分量的关系：如果节点 $x$ 是某个强联通分量在搜索树中遇到的第一个节点，那么这个强连通分量的其他节点肯定在搜索树中以 $x$ 为根的子树中。

Tarjan 算法求强连通分量需要维护两个数组：

$dfn_x$ ：DFS 时节点 $x$ 被遍历的次序。
$low_x$ ：在 $x$ 的子树中能回溯到的最早的在栈里的节点。

使用 DFS 对图中的所有节点进行搜索，维护每个节点的 $dfn$ 和 $low$ 变量，且让搜索到的节点入栈。每找到一个强连通分量，就让这个强连通分量里所有节点出栈。在搜索过程中，对于节点 $x$ 和 $x$ 能直接到达的节点 $y$ 考虑 $3$ 中情况：

$y$ 未被访问：继续对 $y$ 进行搜索。在回溯过程中，用 $low_y$ 对 $low_x$ 进行更新。因为存在从 $x$ 到 $y$ 的直接路径，所以 $y$ 能回溯到的节点 $x$ 也能回溯到。
$y$ 被访问过，已经在栈里：根据 $low$ 的定义，用 $dfn_y$ 更新 $low_x $。
$y$ 被访问过，不在栈里：说明 $y$ 所在的强连通分量已被处理，无需操作。

将上述过程写成代码：

void tarjan(int x)
{
    dfn[x] = low[x] = ++dft;
    st.push(x);
    for(auto y : ver[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(!scc[y])
            low[x] = min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x])
    {
        scc_tot++;
        while(!st.empty())
        {
            int a = st.top(); st.pop();
            scc[a] = scc_tot;
            if(a == x) break;
        }
    }
}

其中 scc[a] 记录节点 $a$ 所属的强连通分量的编号，scc_tot 记录强连通分量总数。

例题

缩点

因为可以重复走，所以走到一个点就可以获得这个点所在的强连通分量里所有点的点权，我们用 Tarjan 算法处理出强连通分量，然后将一个强连通分量看成一个点，点权为强连通分量的点权和，然后跑 DAG 上的 DP 就行了。

P2746 校园网

先考虑第一问：首先进行缩点，对于一个有入度的强连通分量，肯定可以通过发送给其他强联通分量然后传到这里，所以我们只需要对所有入度为 $0$ 的强连通分量发送就行了。

第一问做出来了第二问也就很简单了，显然答案就是入度为 $0$ 的强连通分量个数和出度为 $0$ 的强连通分量个数取 $\min$ 值，注意特判只有 $1$ 个强连通分量的情况就行了。

无向图双联通分量

边双连通：在一张联通的无向图中，对于两个点 $x$ 和 $y$ ，无论删去哪条边，它们都保持联通，就说 $x$ 和 $y$ 边双连通。

点双连通：在一张联通的无向图中，对于两个点 $x$ 和 $y$ ，无论删去哪个点，它们都保持联通，就说 $x$ 和 $y$ 点双联通。

边双连通具有传递性，但点双连通不具有传递性。

Tarjan 算法求边双连通分量

首先我们还是维护 $dfn$ 和 $low$ 变量，对于一条 $x \longleftrightarrow y$ 的边，若 $dfn_x < low_y$ ，则这条边是桥，我们先进行一边 DFS，将所有桥找出来，然后不走桥边进行联通块搜索，这样每一个联通块就是一个边双连通分量。

当然我们也可以仿照求 SCC 时的做法，使用一个栈来维护，当 $dfn_x = low_x$ 时，代表 $x$ 是一个边双的根节点，此时弹出栈里的元素即可。

代码里写的是第二种做法。

void tarjan(int x, int pre)
{
    dfn[x] = low[x] = ++dft;
    st.push(x); inst[x] = true;
    for(int i = head[x]; i; i = e[i].next)
    {
        if((i^1) == pre) continue;
        if(!dfn[e[i].to])
        {
            tarjan(e[i].to, i);
            low[x] = min(low[x], low[e[i].to]);
        }
        else if(inst[e[i].to])
            low[x] = min(low[x], dfn[e[i].to]);
    }
    if(dfn[x] == low[x])
    {
        dcc_tot++;
        while(!st.empty())
        {
            int a = st.top(); st.pop();
            dcc[a] = dcc_tot;
            inst[a] = false;
            if(a == x) break;
        }
    }
}

其中 pre 代表前驱边的编号。

Tarjan算法求点双连通分量

对于一条 $x \longleftrightarrow y$ 的边，若 $dfn_x \le low_y$ ，则 $x$ 是一个割点（如果是搜索树的根节点的话至少需要有两个子树），此时将 $y$ 所属的点双搜索完毕后栈里的元素再加上 $x$ 就构成了一个点双。

void tarjan(int x)
{
    dfn[x] = low[x] = ++dft;
    st.push(x); inst[x] = true;
    bool flag = true; // 是否为孤立点
    for(auto y : ver[x])
    {
        if(y != x) flag = false;
        if(!dfn[y])
        {
            tarjan(y); 
            low[x] = min(low[x], low[y]);
            if(dfn[x] <= low[y])
            {
                dcc_tot++;
                id[dcc_tot].push_back(x);
                while(!st.empty())
                {
                    int a = st.top(); st.pop();
                    id[dcc_tot].push_back(a);
                    inst[a] = false;
                    if(a == y) break;
                }
            }
        }
        else if(inst[y])
            low[x] = min(low[x], dfn[y]);
    }
    if(ver[x].empty() or flag)
    {
        dcc_tot++;
        st.pop();
        inst[x] = false;
        id[dcc_tot].push_back(x);
    }
}