强连通分量（Korasaju & Tarjan）学习笔记

强连通分量（Korasaju & Tarjan）学习笔记

好久以前学过的东西...现在已经全忘了

很多图论问题需要用到强连通分量，还是很有必要重新学一遍的

---

强连通分量（Strongly Connected Component / SCC）

指在一个有向图中，存在的一个顶点集合S，对于所有顶点vi∈S，都保证能够互相到达

环就是最简单的强连通分量之一

但是强连通不等价于简单的环，还有可能是环套环、环套环套环...没有高效的算法很难解决这类问题

---

Korasaju

Korasaju是一个比较直观的解决SCC问题的算法，只需要用到两遍dfs

算法流程如下

（1）假设给定了一个如下的有向图

（2）对于原图进行一遍dfs，并且记录每一个顶点回溯时（★1）的序号（类似于树的后序遍历）

（3）建立一个反向图（将原图所有的边反向）

（4）按顶点dfs回溯序号从大到小（★2）进行rdfs（反向dfs），所有能访问到的顶点同属一个强联通分量

貌似看起来很简单.jpg

【以下是正确性的证明，加深印象用，可以选择跳过】

但是这个算法中有两个第一眼看过去并不容易理解的蛇皮 *** 作

• （★1）：为什么要记录dfs的后序而不是前序？
• （★2）：反向建图后，为什么要按dfs后序从大到小的顺序进行rdfs？

而这正是Korasaju算法的关键

强连通分量的性质是，在同一个分量中的任意两个顶点可以互相到达

对于一个顶点V为起点进行dfs和rdfs，那么V所属的强连通分量S在dfs和rdfs都能被访问到

问题在于，在两次搜索中，有可能有一些本身不在S中的顶点也被访问到了，再通过判断去除这些顶点会使算法的效率降低

那么我们可以考虑以V为起点进行dfs和rdfs一共会出现多少种情形

1. 某一顶点在dfs和rdfs中都被访问到（那么这个顶点就属于V所在的强连通分量S中）
2. 某一顶点在dfs中被访问到，在rdfs中没有访问到
3. 某一顶点在rdfs中被访问到，在dfs中没有访问到

第2、3种情形中的顶点一定不属于强连通分量S，但是如何排除？我们可以考虑通过在rdfs中统计V所在的强连通分量S中的顶点

这样一来，第2种情形

某一顶点在dfs中被访问到，在rdfs中没有访问到

就无需特殊处理了

但是第3种情形

某一顶点在rdfs中被访问到，在dfs中没有访问到

暂时还是没有办法解决

我们可以考虑一下这种典型情形

以1为起点进行dfs，那么不会访问到3 但是以1位起点进行rdfs就会访问到3

但是记录dfs的后序恰好能够解决这样的问题

对于单点进行dfs的过程其实形成了一棵搜索树，由先访问到的顶点（层数较小）指向后访问到的顶点（层数较大）

dfs后序具有这样的性质：对于某搜索树中的一点P，P的dfs后序一定比P的子树中所有顶点的dfs后序大

而对于整个图的dfs就形成了一个搜索树构成的森林，整张图dfs后序最大顶点的总是某一棵树的根R

现在考虑R在反向图中出边的情况（入边即是原图中R的出边，已经在dfs中使用过了）

1. 如果R有出边（R，V），且V在以R为起点dfs的搜索树中 那么V在R所属的强连通分量中
2. 如果R有出边（R，V'），且V'不在在以R为起点dfs的搜索树中 那么在原图中，存在边（V'，R），则R必然在V'所在的搜索树中，与R为某搜索树的根矛盾

所以对R进行rdfs，访问到的顶点全部在R所在的强连通分量中

这时，将这些点从以R为根的搜索树中删去，则搜索树被拆分成森林 根据dfs后序的性质，剩下来所有rdfs未访问的顶点中dfs后序最大的仍是某棵树的根R'

这样一来，Korasaju的正确性得以证明（好绕啊...）

一句话总结算法：建正向、反向图，dfs记录后序，从大到小rdfs

 #include <cstdio>
 #include <cstring>
 #include <vector>
 using namespace std;

 ;

 int n,m;
 vector<int> v[MAX],rv[MAX];

 bool vis[MAX];
 vector<int> ord;

 inline void dfs(int x)
 {
     vis[x]=true;
     ;i<v[x].size();i++)
     {
         int next=v[x][i];
         if(!vis[next])
             dfs(next);
     }
     ord.push_back(x);
 }

 ;
 vector<int> scc[MAX];

 inline void rdfs(int x)
 {
     scc[sz].push_back(x);
     vis[x]=true;
     ;i<rv[x].size();i++)
     {
         int next=rv[x][i];
         if(!vis[next])
             rdfs(next);
     }
 }

 int main()
 {
 //    freopen("input.txt","r",stdin);
     scanf("%d%d",&n,&m);
     ;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         v[x].push_back(y);
         rv[y].push_back(x);
     }

     ;i<=n;i++)
         if(!vis[i])
             dfs(i);

     memset(vis,false,sizeof(vis));
     ;i>=;i--)
     {
         int cur=ord[i];
         if(!vis[cur])
         {
             sz++;
             rdfs(cur);
         }
     }

     ;i<=sz;i++)
     {
         printf("SCC #%d:",i);
         ;j<scc[i].size();j++)
             printf(" %d",scc[i][j]);
         printf("\n");
     }
     ;
 }

输入：

输出：

SCC #:
SCC #:
SCC #:
SCC #: 

---

Tarjan

Tarjan大爷就知道玩dfs，什么算法都是dfs搞出来的orz

这个算法网上讲的也比较全了

我觉得写得比较好的一篇

感觉也就记一记实现方法吧...正确性挺对的但总感觉缺少一点细节

算法流程：

（1）对于每个顶点V维护两个值

• dfn[V]：顶点V的dfs前序
• low[V]：顶点V能到达的节点Pi中，dfn[Pi]的最小值【可能的Pi为当前搜索树中的所有顶点】

（2）访问当前顶点V，idx++（用于统计已经搜索到的顶点数量），dfn[V]=idx，先给low[V]初值idx，将V压入栈

（3）访问与V有边（V，Ui）且没有被访问过的顶点Ui；借助与V有边（V，Ui'）且已在栈中的顶点Ui'更新low[V]的值，low[V]=min{ low[V] , dfn[Ui'] }（这里其实dfn[Ui']==low[Ui']）

（4）借助所有Ui，更新low[V]的值，low[V]=min { low[V] , low[Ui] }

（5）判断：如果low[V]==dfn[V]，则栈中的所有顶点同属一个强连通分量，则全部d出栈；否则当无事发生（笑）

【简单分析一下正确性，可跳过】

整个图是由很多坨（有多个顶点的）强连通分量和伸出/伸入的“触须”构成的

• 如果是单纯的一坨强连通分量，那么显然子树中的任意点都可以通过一些边回到层数更小的点，从而避免被单独d出当做强连通分量
• 如果这一坨强连通分量有伸出的“触须”，那么“触须”上的所有点均无法访问到层数更小的点，会被依次d出
• 如果有伸入这一坨强连通分量的“触须”，那么强连通分量中的所有点均无法访问到“触须”上的点，会在强连通分量d出后被依次d出

 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <vector>
 using namespace std;

 ;

 int n,m;
 vector<int> v[MAX];

 int index;
 int dfn[MAX],low[MAX];
 bool in[MAX];
 vector<int> stack;

 int sz;
 vector<int> scc[MAX];

 void Tarjan(int x)
 {
     dfn[x]=low[x]=++index;
     in[x]=true;
     stack.push_back(x);

     ;i<v[x].size();i++)
     {
         int next=v[x][i];

         if(!dfn[next])
         {
             Tarjan(next);
             low[x]=min(low[x],low[next]);
         }
         else
             if(in[next])
                 low[x]=min(low[x],dfn[next]);
     }

     if(low[x]==dfn[x])
     {
         sz++;
         int y;
         do
         {
             y=stack.back();
             stack.pop_back();
             in[y]=false;
             scc[sz].push_back(y);
         }
         while(y!=x);
     }
 }

 int main()
 {
 //    freopen("input.txt","r",stdin);
     scanf("%d%d",&n,&m);
     ;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         v[x].push_back(y);
     }

     ;i<=n;i++)
         if(!dfn[i])
             Tarjan(i);

     ;i<=sz;i++)
     {
         printf("SCC #%d:",i);
         ;j<scc[i].size();j++)
             printf(" %d",scc[i][j]);
         printf("\n");
     }
     ;
 }

---

SCC往往是其他图论算法的一个子任务，就不单独找题练了（模板题NOIP2015 D1T2）

（完）