tarjan模板校园的题目

//
//main.cpp
//Chapter 1
//
//Created by chengzhi lin on 2018/3/6.
//Copyright ? 2018年 lczazu. All rights reserved.
//
#include
#include
#include
#include
#include
#include
#define MAXN 100005
using namespace std;

int _index;
int shelter[ MAXN ] = { 0 };
int polute[ MAXN ] = { 0 };
int vis_time = 0;
int cmp_num = 0;
int low[ MAXN ];
int dfn[ MAXN ];
vector graph[ MAXN ];
vector cmp[ MAXN ];
int in_cmp[ MAXN ];
int out_degree[ MAXN ] = { 0 };
bool in_stack[ MAXN ] = { 0 };
stack sta;

void init( )
{
memset( low, -1, sizeof( low ) );
memset( dfn, -1, sizeof( dfn ) );
}

void tarjan( int x )
{
//cout << "x " << x << endl;
dfn[ x ] = low[ x ] = vis_time++;
in_stack[ x ] = true;
sta.push( x );

for( int i = 0; i < graph[ x ].size( ); ++i )
{
int y = graph[ x ][ i ];

if( dfn[ y ] == -1 )
{
tarjan( y );
low[ x ] = min( low[ x ], low[ y ] );
}
else
{
【tarjan模板】if( in_stack[ y ] )
{
low[ x ]= min( low[ x ], dfn[ y ] );
}
}
}

if( low[ x ] != dfn[ x ] )
{
return;
}

int y;
do
{
y = sta.top( );
sta.pop( );

in_stack[ y ] = false;
cmp[ cmp_num ].push_back( y );
in_cmp[ y ] = cmp_num;
}while( y != x );

cmp_num++;
}

void add( int a, int b )
{
graph[ a ].push_back( b );
}

void set_degree( )
{
for( int i = 0; i < _index; ++i )
{
int temp = in_cmp[ i ];

for( int j = 0; j < graph[ i ].size( ); ++j )
{
if( in_cmp[ graph[ i ][ j ] ] == temp )
{
continue;
}

++out_degree[ temp ];
}
}
}
int main(int argc, const char * argv[]) {

init( );
for( int i = 0; i < _index; ++i )
{
if( dfn[ i ] == -1 )
{
tarjan( i );
}
}

set_degree( );
return 0;
}

tarjan模板

推荐阅读

肠衣是什么东西肠衣是啥东西

雨中冒险2神器雨中冒险2early

安卓杀毒软禁啊,安卓杀毒软件金山卫手机版好用吗?

春分农事多农时耽不起

柠檬蜂蜜水的功效柠檬蜂蜜水的功效与作用

如何将人物照片制作成黑白矢量图

旗舰版

土方法|手表怎么消磁土方法！

发包机国外服务器设置教程，vps发包机

mysql锁失效 mysql超时线上解锁

一些特别想记录下来的东西

肉羊酮尿病是怎样一种病

平易之药愈重症

怎么恢复汉王人脸识别考勤机出厂设置？汉王人脸考勤机显示位置吗

笔墨纸砚什么意思词语笔墨纸砚什么意思

吉祥结有何寓意？你知道吗?

对联如何区分左右对联左右怎么区分呢？

华容一中校训华容一中公众号

抑郁症|快乐的人也会得抑郁｜关于抑郁症的 10 个真相

女性经期吃什么能减肥？女性经期吃什么可以减肥