【图论】强连通分量

前言

在学习该部分之前，请熟悉此部分的概念。我们使用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——如果子节点可以回溯到更上面的结点，那它们也可以。

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

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，下面是实现代码：

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是一个好东西

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缩点后图的示例：

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); // 放入队列
            }
        }
    }
}

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

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都缩成一个点，然后找到这个新图的焦点输出里面的元素数量就好了。关于上面两个方法，我个人更喜欢第一个，毕竟不需要新建图而且完美避免了重边和自环的影响。

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

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

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

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");