首页 > 代码库 > tarjan算法求强连通分量
tarjan算法求强连通分量
先上代码：
#include <iostream>#include <cstring>#include <vector>#include <stack>using namespace std;int G[1000][1000];int pre[1000],sccno[1000],lowlink[1000]; //sccno[u]:u节点所属于的强连通分量序号
int dfs_clock,scc_cnt,n,m,x,y; //pre[u]:u节点的时间戳stack<int> S; //lowlink[u]:由u节点所能追溯到的最早的点的时间戳void dfs(int u){ pre[u]=lowlink[u]=++dfs_clock; S.push(u); for (int i=1;i<=G[u][0];i++) { int v=G[u][i]; if (!pre[v]) { dfs(v); lowlink[u]=min(lowlink[u],lowlink[v]); } else if (!sccno[v]) { lowlink[u]=min(lowlink[u],pre[v]); } } if (lowlink[u]==pre[u]) //说明找到了一个新的连通分量 { scc_cnt++; for (;;) { int x=S.top(); S.pop(); sccno[x]=scc_cnt; if (x==u) break; } }}void find_scc(int n){ dfs_clock=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(pre,0,sizeof(pre)); for (int i=1;i<=n;i++) if (!pre[i]) dfs(i); //pre[i]==0说明还没搜索过i点}int main(){ cin>>n>>m; memset(G,0,sizeof(G)); for (int i=1;i<=m;i++) { cin>>x>>y; G[x][0]++; //使用邻接表记录图 G[x][G[x][0]]=y; } find_scc(n); cout<<scc_cnt<<endl; for (int i=1;i<=n;i++) cout<<sccno[i]<<" "<<pre[i]<<endl; return 0;}
Reference：
http://blog.csdn.net/xinghongduo/article/details/6195337
http://blog.csdn.net/xinghongduo/article/details/6196292
代码中用到了STL栈容器，可参考这里：
http://blog.csdn.net/wallwind/article/details/6858634
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。