【图论】强连通分量

Mon Jun 26 2023

13 minutes

2809 words

前言#

在学习该部分之前，请熟悉此部分的概念。我们使用 Tarjan 算法求解时要用到的概念有：DFS 树，DFS 森林，DFS 序，以及其中的树边，前向边，返租边与横叉边。了解它们有助于读者理解 Tarjan 的工作原理。

概念#

子图的定义#

假设有 $G\:=<V,E>G^{\prime}=<V^{\prime},E^{\prime}>$ 两个图 $V^{\prime}\subseteq V$ 且 $E^{\prime}\subseteq E$ ，则我们称 $G'$ 是 $G$ 的子图。记作 $G^{\prime}\subseteq G$ 。

什么是连通分量#

无向图中，如果在子图 $G'$ 中所有的结点 $u$ 与 $v$ 之间都有通路，且无法再加入任何一个新的点使之满足，则我们称子图 $G'$ 是母图的一个连通分量。（此时 $G'$ 是一个极大图）
有向图中，若仍然满足上述定义，则称子图 $G'$ 是母图的一个强连通分量。（简称SCC）

Tarjan 算法#

理论前提#

因为每一个强连通分量都不可以再加入任意一个新的点，显然每一个强连通分量都是独立的，不存在相交的情况。而且强连通分量作为一个子图，显然也是DFS 树中的一颗子树，自然地，我们可以通过对 DFS 树不断剪切 SCC 达到求解 SCC 的目的。

那么什么时候要剪去 SCC 呢？我们分析剪切 DFS 树的过程，首先我们要找到一个 SCC 中 DFS 树的顶点，这个顶点是 SCC 的入口，在只有树边的 DFS 树中，它在 SCC 中的入度为 0，可以代表整个 SCC，作为剪切的入口。

那么问题变成了如何寻找顶点。我们知道在 DFS 树中存在返祖边，同时我们知道在环上的所有结点都是强连通分量的一部分，因为环上的结点都可以达到环上的任意一个点。那么我们就可以断定存在返租边的结点一定不是顶点，因为它们对于上面的一个结点存在于同一个强连通分量中——这同时说明了这两点之间的所有结点都在同一个强连通分量中（构成了一个环）。

当然，这样是不够的，因为我们还存在着横叉边，这导致 DFS 树中的不同子树存在了联系——有可能和别的子树构成环。（其实是不可能的，因为那个时候横叉边其实就是树边）

试着假设情况，第一种情况就是当我们遍历到这一条横叉边时它所指向的结点已经被遍历过且没有被剪切，这说明什么？说明这个结点和指向的结点一定在一条连通的树边上。为什么呢？假设下面的情况：你说遍历 5 结点的时候 4 结点存在吗？肯定是不存在的，因为 4 就是一个顶点，在回溯的时候就被剪切了。拿遍历 3 结点的时候 2 结点存在吗？肯定也是不存在的，2 结点本身就是一个强连通分量，在回溯的时候就被剪切了。所以在这种情况下只有与 4，6，7 三个结点一样，是强连通分量，因此这个结点也不是顶点。（实质上此时的横叉边就是返祖边）

第二种情况是遍历到这一条横叉边时它所指向的结点已经被遍历过且被剪切了。那这种情况就类似与上图的 5，3 结点，基于强连通分量的独立性，这个结点与它指向的结点并无关系，直接跳过。

第三种情况是结点还没有被遍历，这个就不一样了。因为是深度优先算法，这种情况是的边并不是横叉边，而是树边，直接跳过。

回顾处理这两种边的情况，会发现只有结点已经被遍历过且没有被剪切时此结点才不是顶点——也就是存在 SCC，那么我们就好处理了，只需要一次 DFS 就可以完成。至此理论完备，实践开始。

注意这中间的结点其实都是 SCC 的一部分，比如上图的 6 是 4，7 中的一部分

算法实现#

关于邻接表的存图方式在【数据结构】邻接表与链式前向星

首先我们使用邻接表存图，之后在新的 namespace 中开始编写我们的代码：

找寻顶点#

因为我们题目的结点编号不方便直接拿来使用求解顶点（因为顶点的编号可能很大也可能很小，我们不能在这里浪费时间），这里我选择定义一个 $dfn$ 数组存贮每个结点的 DFS 序，那么越上面的结点 DFS 序越小，我们就可以使用 min 直接得到结点序了。

同时定义一个数组 $up$ 存储一个结点能够回溯到的结点，也就是一个结点通过返租边与横叉边能够回到的结点。通过上面的分析我们知道顶点的 $up$ 就是它们自己，因此我们只需要判断 $up$ 是否等于 $dfn$ 就可以判断结点是不是顶点。

然后由我们上面的分析，添加一个 $vis$ 数组记录此结点有没有被剪切，那么判断条件就变成->如果这个结点还没有被遍历，进入。否则判断它有没有被剪切，如果没有被剪切，就更新现在的 $up$ 数组。

最后不要忘记夹在环中间的结点，我们在 DFS 回溯的时候让他们取子节点 $up$ 的 min——如果子节点可以回溯到更上面的结点，那它们也可以。

至此我们可以写出下面的寻找代码：

CPP

vector<vector<int>> g(N); // 邻接表存图

namespace SCC
{
    int dfn[N], up[N], crd = 0;
    bool vis[N];

    void dfs(int x)
    {
        dfn[x] = up[x] = ++crd; // 初始化结点
        vis[x] = true; // 标记结点存在
        for(int y : g[x])
        {
            if(!dfn[y]) // 如果结点y没有被遍历
            {
                dfs(y); // 进入递归
                up[x] = min(up[x], up[y]); // 回溯时更新
            }
            else // 如果已经被更新同时存在
                if(vis[y]) up[x] = min(up[x], up[y]);
        }
    }
}

存贮 SCC#

因为是 DFS 遍历，我们不如把遍历到的结点都存在一个栈中，树边串联了整个 SCC，我们可以通过栈的出入存储 SCC。

首先明确代码位置，我们要在回溯之后再执行添加操作。此时整个结点下面的结点（除了被剪切的）都已经存在栈中。如果 x 是顶点，那么由我们顶点代表SCC的思路，此时 x 与它后面的部分就是 SCC 所包含的部分。得益于剪切的思路，栈中在 x 后面的部分不会包含其他的 SCC（因为在其溯回时已经剪切了）。那我们只需要不断取出栈中元素直到 x 并添加进 vector，就完成了一次添加操作。

我使用数组 $stk$ 模拟栈，用变量 $top$ 表示栈头，声明vector<vector<int>> scc存储 SCC。为了泛用，使用数组 $bel$ 记录结点 y 属于哪个 SCC，下面是实现代码：

CPP

if(dfn[x] == up[x]) // 如果此时x是顶点
{
    vector<int> c; // 新建一个临时容器
    while(true)
    {
        int y = stk[top--]; // 取出栈头
        vis[y] = false; // 去掉y的存在标记
        bel[y] = scc.size(); // 记录y属于哪个SCC
        c.push_back(y); // 添加进临时容器
        if(y == x) break; // 如果x被取出了，退出
    }
    scc.push_back(c); // 加入SCC
}

完整代码#

至此，我们的 Tarjan 算法就完成了，只要using namespace SCC就可以使用了。

namespace 是一个好东西

CPP

vector<vector<int>> g(N); // node_vector

namespace SCC
{
    vector<vector<int>> scc;
    // dfs_list / all_up / scc_style / now_crd
    int dfn[N], up[N], bel[N], crd = 0;
    // node_list / list_crd
    int stk[N], top = 0;
    bool vis[N];

    void dfs(int x)
    {
        dfn[x] = up[x] = ++crd; // init x
        stk[++top] = x; // enter x
        vis[x] = true;
        for(int y : g[x])
        {
            if(!dfn[y]) // y not have
            {
                dfs(y);
                up[x] = min(up[x], up[y]);
            }
            else
                if(vis[y]) up[x] = min(up[x], up[y]);
        }
        if(dfn[x] == up[x]) // if x == x
        {
            vector<int> c; // make a new scc
            while(true)
            {
                int y = stk[top--]; // pop stk
                vis[y] = false; // cut y
                bel[y] = scc.size();
                c.push_back(y);
                if(y == x) break;
            }
            scc.push_back(c);
        }
    }
}

例题#

B3609 强连通分量#

题目链接：B3609 [图论与代数结构 701] 强连通分量

纯纯 Tarjan 例题，题目中黑体字标出的重边和自环并不会影响 Tarjan 的正确性。

需要注意的是要从小到大输出 SCC，用优先队列或者 sort 都可以，比较简单的一道绿题。

P2341 受欢迎的牛 G#

题目链接：P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

此题运用了 SCC 的用途之一——缩点。

因为在一个 SCC 中的所有结点都可以不受限制的到达任意一个结点，所以在有些情况下可以把这一堆点的集合直接看成一个点来处理。

对于缩点的方案，有下面两个：

第一种，不建立新图，通过一个变量处理重边。下面是通过 BFS 遍历 SCC 缩点后图的示例：

CPP

void bfs(int i) // 入口
{
    node.push(i); // 放入队列
    while(!node.empty())
    {
        int u = node.front(); // 取出队头
        ins[u] = ++t; // 打上标记
        node.pop();
        for(int x : SCC::scc[u]) // 在这个SCC中取点
        {
            for(int y : g[x]) // 向外扩展
            {
                int nxt = SCC::bel[y]; // 获得这个结点的SCC结点
                if(ins[nxt] == t) continue; // 如果标记相同跳过
                ins[nxt] = t; // 打上相同的标记防止重复遍历
                node.push(nxt); // 放入队列
            }
        }
    }
}

第二种，新建一个新图，下面是新建图的示例：

CPP

vector<vector<int>> h(N); // 定义新图
for(int i = 1; i <= n; i++)
   for(int y : g[i])
       if(SCC::bel[i] != SCC::bel[y])
           h[SCC::bel[i]].push_back(SCC::bel[y]); // 加边

比如这一道题目，我们只需要把所有的 SCC 都缩成一个点，然后找到这个新图的焦点输出里面的元素数量就好了。关于上面两个方法，我个人更喜欢第一个，毕竟不需要新建图而且完美避免了重边和自环的影响。

不过我们并不需要遍历图，可以用更巧妙的方法

因为题目中要求是所有奶牛喜欢，所以我们只要找出度为零的结点就好啦！注意一下是所有奶牛喜欢，因此如果有两个出度为零的结点，此题目就无解了，注意判断！

下面是统计出度和结果的代码：

CPP

int deg[N]; // 结点N的出度
int cnt, ans; // 如果cnt > 1说明数据无解
for(int i = 1; i <= n; i++)
    for(int y : g[i]) // 如果两个SCC不同，给父节点的出度++
        if(bel[y] != bel[i]) deg[bel[i]]++;

for(int i = 0; i < scc.size(); i++)
    if(!deg[i]) { cnt++; ans += scc[i].size(); }

if(cnt == 1) printf("%d", ans);
else printf("0");

【图论】强连通分量

https://frosti.saroprock.com/blog/强连通分量/