一、知识储备
强连通： 在一个有向图G里，设两个点 a 、b，发现由a有一条路可以走到b，由b又有一条路可以走到a，我们就叫这两个顶点（a，b）强连通。
强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。
强连通分量：在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就把这个子图叫做强连通分量。
参考博客：强连通算法——Tarjan个人理解+讲解
参考博客：全网最详细tarjan算法讲解
二、算法描述
tarjan算法，之所以用DFS，是因为它将每一个强连通分量作为搜索树（即有向图）上的一个子树。而这个图，就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。
每个节点都有两个参数（用数组表示）：
① DFN［］ 记录搜索到该点的时间，也就是第几个搜索这个点的；
② LOW［］记录该点所在的（强连通分量扮演的）搜索子树的根节点的DFN值。
过程：
- 数组的初始化：当首次搜索到点p时，DFN与LOW数组的值都为到该点的时间；
- 堆栈：每搜索到一个点，将它压入栈顶；
- 当点p有与点p’相连时，如果此时（时间为DFN[p]时）p’不在栈中，p的low值为两点的low值中较小的一个；
- 当点p有与点p’相连时，如果此时（时间为DFN[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个；
- 当搜索到一个点的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量；
- 继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。
帮助领悟：
- 我们用LOW值记录该点所在强连通子图对应的搜索子树的根节点的DFN值。注意，该子树中的元素在栈中一定是相邻的，且根节点在栈中一定位于所有子树元素的最下方；
- 强连通分量是由若干个环组成的。所以，当有环形成时（也就是搜索的下一个点已在栈中），我们将这一条路径的low值统一，即这条路径上的点属于同一个强连通分量；
- 如果遍历完整个搜索树后某个点的dfn值等于low值，则它是该搜索子树的根。这时，它以上（包括它自己）一直到栈顶的所有元素组成一个强连通分量；
- 当一个点既是强连通子图Ⅰ中的点，又是强连通子图Ⅱ中的点，则它是强连通子图Ⅰ∪Ⅱ中的点；
- Tarjan算法基于定理：在任何深度优先搜索中，同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。
代码：
void tarjan(int u) //此代码仅供参考
{
vis[u]=1;
low[u]=dfn[u]=cnt++;
for(int i=0;i<mp[u].size();i++)
{
int v=mp[u][i];
if(vis[v]==0)Tarjan(v);
if(vis[v]==1)low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
sig++;
}
}
三、代码实现
#include<stdio.h>//此代码仅供参考，用于求一个图存在多少个强连通分量
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 1000000
vector<int >mp[maxn];
int ans[maxn];
int vis[maxn];
int dfn[maxn];
int low[maxn];
int n,m,tt,cnt,sig;
void init()
{
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)mp[i].clear();
}
void Tarjan(int u)
{
vis[u]=1;
low[u]=dfn[u]=cnt++;
for(int i=0;i<mp[u].size();i++)
{
int v=mp[u][i];
if(vis[v]==0)Tarjan(v);
if(vis[v]==1)low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
sig++;
}
}
void Slove()
{
tt=-1;cnt=1;sig=0;
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
Tarjan(i);
}
}
printf("%d
",sig);
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)break;
scanf("%d",&m);
init();
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x].push_back(y);
}
Slove();
}
}
//测试数据
/*
7 9
1 2
2 3
3 1
2 4
4 7
7 4
4 5
5 6
6 4
8 10
1 2
2 3
3 1
2 4
4 7
7 4
4 5
5 6
6 4
7 8
*/
四、沙场练兵
题目一、迷宫城堡
题目二、Popular Cows