文章目录
前言
图论——强连通分量（Tarjan算法)
tarjan可以做什么？
根据 Robert Tarjan 的名字命名的算法Tarjan算法可以在线性时间内求出无向图的割点与桥，再进一步的求出双联通分量，也在数据结构上做出了贡献。
Tarjan算法的用途：
- 求桥和割点
- 求点和边的双连通分量
- 求强连通*
.
一、Tarjan求强连通分量
“有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量（strongly connected component）。” ————来自百度
也就是在图中找到一个最大的图，使这个图中每个两点都能够互相到达。这个最大的图称为强连通分量，同时一个点也属于强连通分量。
Tarjan算法，之所以使用深度优先搜索（DFS）就是因为它将每一个强连通分量作为搜索树上的一个子树。而这个图，就是一个完整的搜索树。
为了使这颗搜索树在遇到强连通分量的节点的时候能顺利进行。每个点都有两个参数。
1，DFN［］作为这个点搜索的次序编号（时间戳），简单来说就是 第几个被搜索到的。％每个点的时间戳都不一样％。
2，LOW［］作为每个点在这颗树中的，最小的子树的根，每次保证最小，like它的父亲结点的时间戳这种感觉。如果它自己的LOW［］最小，那这个点就应该从新分配，变成这个强连通分量子树的根节点。
ps：每次找到一个新点，这个点LOW［］＝DFN［］。
而为了存储整个强连通分量，这里挑选的容器是，堆栈。每次一个新节点出现，就进站，如果这个点有 出度 就继续往下找。直到找到底，每次返回上来都看一看子节点与这个节点的LOW值，谁小就取谁，保证最小的子树根。如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。）最后找到强连通分量的节点后，就将这个栈里，比此节点后进来的节点全部出栈，它们就组成一个全新的强连通分量。
二、具体代码
#define MAXN 1000
//#define MAXM 1000*2;
int n,m;//n表示节点数量,m表示路径数量
int dfn[MAXN];//时间戳
int low[MAXN];//子树中连通的最小dfn
bool vis[MAXN];//判断是否走过
int color[MAXN];//给予同一颜色,表示为同一强连通分量
vector <int > node[MAXN];//邻接表
stack<int> Stack;//栈存储连通点
//index:节点编号 sum：强连通分量数目
int index,sum;
void Farjan(int v){
dfn[v]=low[v]=++index; //(1)初始化dfn数组，同时将low设置为相同值
vis[v]=1;//表示走过该点
Stack.push(v);//储存走过点
for(int i=0;i<node[v].size();++i){//(2)遍历所有可能到达的点
int j=node[v][j];
if(!dfn[j]){//如果这个点从没访问过，则先放问它，再用它更新low[v]的值
Farjan(j);
low[v]=min(low[j],low[v]);//更新所能到的上层节点
}
else{//不在栈中的点，要么没有访问，要么不能到达id，所以只需要判断栈中的
if(vis[j]) low[v]=min(low[v],dfn[j]);
}//DFN是栈中编号或时间戳，如果j在栈中，则v到栈中最上端节点为DFN[j]
}
if(dfn[v]==low[v]){//(3)自己和子节点形成了强连通分量，或者只有自己孤身一人
++sum;
color[v]=sum;
int y;
do{
y=Stack.top();
printf("%d ",y);
Stack.pop();
color[y] = sum;//给予同一颜色,表示为同一强连通分量
vis[y] = 0;//出栈要顺便修改vis
}while(y!=v);//将从v开始所有的点取出
printf("\n");
}
return ;
}
输入格式
void Solve(){
//init();
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
memset(color,0,sizeof(color));
while( !Stack.empty() )
Stack.pop();
index=0,top=0,sum=0;
for(int i=1;i<=n;++i){//寻找个点
if(!dfn[i])
Farjan(i);
}
printf("%d\n", sum);
for(int i = 1 ; i <= n ; ++ i )
node[i].clear() ;
}
int main(){
while(~scanf("%d%d",&n,&m)&&n){
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
node[x].push_back(y);
}
Solve();
}
return 0;
}