• 大小: 2KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-06-10
  • 语言: C/C++
  • 标签: 关于  tarjan  算法  

资源简介

关于tarjan算法的代码,自己写的,和大家分享,希望大家能多多指教

资源截图

代码片段和文件信息

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int const N=20001;
stacks;
vectormap[N]newmap[N];
bool inStack[N];
int dfsOrder[N]low[N]newOrder[N];
int nodeSCC;
void tarjan(int x)
{
    dfsOrder[x]=low[x]=++node;
    s.push(x);
    
    int u;
    if(map[x].empty()==false)
    for(int i=0;i    {
        u=map[x].at(i);      
        if(inStack[u])      
        if(dfsOrder[u]==0)
        {
          tarjan(u);
          low[x]=min(low[u]low[x]);           
        }
        else 
        {
          low[x]=min(low[x]dfsOrder[u]);     
        }   
    }
     
    if(dfsOrder[x]==low[x])
      {
          SCC++;
          while(s.top()!=x)
          {
              newOrder[s.top()]=SCC;
              inStack[s.top()]=false;
              s.pop();               
          }
          newOrder[x]=SCC;
          inStack[x]=false;
          s.pop();                  

评论

共有 条评论