强连通分量Kosaraju、Tarjan【模板】

本文主要是介绍强连通分量Kosaraju、Tarjan【模板】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
把一个图变为一个强连通图需要添加边数：先求出原图的强连通分量，缩点后变为有向无环图，计算新图入度为0的点的个数SumIn和出度为0的点的个数SumOut，答案就是max(SumIn，SumOut)。
Kosaraju算法：
1.对原图进行第一遍深度优先遍历，记录下每个节点的离开时间num[i]。
2.对原图的反向边构成的图进行第二遍深度优先遍历，从步骤(1)中离开时间最晚的点开始。第(2)步中每搜索到一棵树都是一个强连通分量Hash[]把同一连通分量上的点缩成一个点。
3.缩点之后的图就构成了DAG(有向无环图)，树的个数就是强连通分量的个数。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 10010;
const int MAXM = 50050;struct EdgeNode
{int to; int next1;int fr;int next2;
}Edges[MAXM];int Head1[MAXN],Head2[MAXN],vis[MAXN];
int num[MAXN],Hash[MAXN],Count[MAXN],outdegree[MAXN];
int id;
//Head1[],Head2[]分别存原图和反图
//num[i]记录每个节点离开时间
//vis[i]用来记录某个点是否被访问过
//Count[sig]统计每个连通分量sig中的点个数
//Hash[cur]用来将同一个联通分量中的点cur(都属于一个sig)缩成一个点sig
void AddEdges(int u,int v)
{Edges[id].to = v;Edges[id].next1 = Head1[u];Head1[u] = id;Edges[id].fr = u;Edges[id].next2 = Head2[v];Head2[v] = id++;
}
//DFS第一遍，求出记录每个节点离开时间num[i]
void DfsOne(int cur,int& sig)
{vis[cur] = 1;for(int i = Head1[cur]; i != -1; i = Edges[i].next1){if( !vis[Edges[i].to] )DfsOne(Edges[i].to,sig);}num[++sig] = cur;
}
//DFS第二遍，求出双联通分量
void DfsTwo(int cur,int sig)
{vis[cur] = 1;Hash[cur] = sig;    //Hash[]用来将同一个联通分量中的点(都所欲一个sig)缩成一个点Count[sig]++;       //Count[]统计每个连通分量中的点个数，sig为强连通分量个数for(int i = Head2[cur]; i != -1; i = Edges[i].next2){if( !vis[Edges[i].fr])DfsTwo(Edges[i].fr,sig);else if(Hash[Edges[i].fr] != Hash[cur])     //outdegree判断缩点后新图各点是否有出度，特殊题目要求outdegree[Hash[Edges[i].fr]] = 1;}
}int Kosaraju(int N)
{int sig = 0,ans;memset(vis,0,sizeof(vis));//第一次深度优先搜索for(int i = 1; i <= N; ++i) //DFS求得拓扑序列num[]if( !vis[i] )DfsOne(i,sig);  //sig为强连通个数memset(vis,0,sizeof(vis));memset(Count,0,sizeof(Count));memset(outdegree,0,sizeof(outdegree));//第二次深度优先搜索int i = sig;sig = 0;for(; i >= 1; --i)  //按照拓扑序列进行第二次dfsif( !vis[num[i]])DfsTwo(num[i],++sig);//算法结束，以下为特殊题目要求int temp = 0;for(int i = 1; i <= sig; i++)   //新图只有一个点出度为0才算有解，特殊题目要求if(!outdegree[i]){temp++;ans = Count[i];}//printf("$%d ",temp);if(temp == 1)return ans;elsereturn 0;
}int main()
{int N,M,u,v;while(~scanf("%d%d",&N,&M)){id = 0;memset(Head1,-1,sizeof(Head1));memset(Head2,-1,sizeof(Head2));for(int i = 0; i < M; ++i){scanf("%d%d",&u,&v);AddEdges(u,v);}int ans = Kosaraju(N);printf("%d\n",ans);}return 0;
}

Tarjan算法：

访问一个没有被访问过的节点v；否则结束。
初始化dfn[v]和low[v]。
对于节点v的所有邻接顶点u：
1. 如果没有访问过，转到步骤(2)，同时维护low[v]。
2. 如果访问过，但没有删除，维护low[v]。
  如果low[v] == dfn[v]，那么取出相应的强连通分量。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 10010;
const int MAXM = 50050;struct EdgeNode
{int to;int next;
}Edges[MAXM];int Head[MAXN],vis[MAXN],low[MAXN];
int dfn[MAXN],Stack[MAXN],outdegree[MAXN],Count[MAXN],m,id;
//dfn[v]表示顶点v被访问的时间
//low[v]为与顶点v邻接的未删除的顶点u的low[u]和low[v]的最小值
void AddEdges(int u,int v)
{Edges[id].to = v;Edges[id].next = Head[u];Head[u] = id++;
}int TarBFS(int pos,int lay,int &scc)
{vis[pos] = 1;low[pos] = lay;     //初始为开始时间dfn[pos] = lay;     //初始为开始时间Stack[++m] = pos;   //将当前未处理节点入栈，回溯时可以判断栈顶到栈中的结点是否为同一个强连通分量//如果当前节点是一个强连通分量的根，它的强连通分量一定是以该根为根节点的(剩下节点)子树for(int i = Head[pos]; i != -1; i = Edges[i].next)  //枚举每一条边{if(!vis[Edges[i].to])TarBFS(Edges[i].to,++lay,scc);if(vis[Edges[i].to] == 1)low[pos] = min(low[pos],low[Edges[i].to]);}//dfn[pos] == low[pos]，则当前顶点就是一个强连通分量if(dfn[pos] == low[pos])    //缩点，low[]相同的结点属于同一个强连通分量{++scc;//强连通分量个数do{Count[scc]++;       //记录每个强连通分量内的点数low[Stack[m]] = scc;vis[Stack[m]] = 2;}while(Stack[m--] != pos);}return 0;
}int Tarjan(int N)
{int scc = 0, temp = 0, ans, lay = 1;m = 0;memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));for(int i = 1; i <= N; ++i) //一次DFS求出强连通分量if(vis[i] == 0)TarBFS(i,lay,scc);  //scc得出强连通分量个数//下边为特殊题目要求，如果只有一个入度为0的点，则得到for(int i = 1; i <= N; ++i){for(int j = Head[i]; j != -1; j = Edges[j].next)if(low[i] != low[Edges[j].to]){outdegree[low[i]] = 1;//标记入度不为0的点break;/*outdegree[low[i]]++;  indegree[low[Edges[j].to]]++;  //记录入度和出度不为0的点*/}}for(int i = 1; i <= scc; ++i){if(! outdegree[i])  //得到入度不为0的点个数{if(++temp > 1)break;ans = Count[i];}}if(temp != 1)return 0;return ans;
}
int main()
{int N,M,u,v;while(~scanf("%d%d",&N,&M)){memset(Head,-1,sizeof(Head));memset(outdegree,0,sizeof(outdegree));memset(Count,0,sizeof(Count));id = 0;for(int i = 0; i < M; ++i){scanf("%d%d",&u,&v);AddEdges(u,v);}int ans = Tarjan(N);printf("%d\n",ans);}return 0;
}