SCC Tarjan算法

本文主要是介绍SCC Tarjan算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

int dfs_clock,scc_cnt;
int low[maxn],dfn[maxn],sccno[maxn];  //sccno[i]为i所在的SCC编号
stack<int>S;
vector<int>map[maxn];
void tarjan( int u, int fa )
{low[u] = dfn[u] = ++dfs_clock;S.push(u);for( int i = 0; i < map[u].size(); i ++ ){int v = map[u][i];if( !dfn[v] ){tarjan( v,u );low[u] = low[u] <= low[v] ? low[u]:low[v];   //用后代low更新自己}else if( !sccno[v] )     //用反向边更新自己{low[u] = low[u] <= dfn[v] ? low[u]:dfn[v];}}if( low[u] == dfn[u] ){scc_cnt ++;for(;;){int x = S.top(); S.pop();sccno[x] = scc_cnt;if( x == u )break;}}
}void find_scc()
{dfs_clock = scc_cnt = 0;while( !S.empty() )	S.pop();  memset( low,0,sizeof(low) );memset( dfn,0,sizeof(dfn) );memset( sccno,0,sizeof(sccno) );for( int i = 0; i < n; i ++ ){if( !dfn[i] )tarjan( i,-1 );}
}

这篇关于SCC Tarjan算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---