强连通tarjan模版

#include<stdio.h>

#include<iostream>

#include<math.h>

#include<queue>

#include<vector>

#include<string.h>

#include<algorithm>

#include<stack>

#define N 1000

#define INF64 1152921504606846976

#define INF32 2147483647

#define ll int

using namespace std;

vector<int>G[N],Tarjan[N];//Tarjan从0开始存下所有的强连通，其大小用 tar记录,注意分量中只有一个点时，则不连通（Tarjan[tar]<2 则应该为0 )

stack<int>mystack;

int n,m,tar;

int DFN[N],Low[N],Time;// 小写的time会redeclared

bool instack[N],vis[N];

inline ll Max(ll a,ll b){return a>b?a:b;}

inline ll Min(ll a,ll b){return a<b?a:b;}

void tarjan(int u){

	int v;

	DFN[u]=Low[u]=++Time;

	mystack.push(u);  instack[u]=true;

	vis[u]=true;

	for(int i=0;i<G[u].size();i++)//遍历u的所有子节点

	{

		v=G[u][i];

		if(!DFN[v])

		{

			tarjan(v);

			Low[u]=Min(Low[u],Low[v]);

		}

		else if(instack[v])

			Low[u]=Min(Low[u],DFN[v]);

	}

	if(DFN[u]==Low[u])

	{

		do

		{

			v=mystack.top();	mystack.pop();  instack[v]=false;

			Tarjan[tar].push_back(v);

		}while(u!=v);

		tar++;

	}

}

void InitTar(){

	memset(DFN,0,sizeof(DFN));	memset(Low,0,sizeof(Low));

	memset(instack,0,sizeof(instack));

	memset(vis,0,sizeof(vis));//标记已搜过的点

	while(!mystack.empty())mystack.pop();

	for(int i=0;i<n;i++)Tarjan[i].clear();

	tar=Time=0;

}

int main(){

	int i,j;

	while(~scanf("%d%d",&n,&m)){

		for(i=0;i<n;i++)G[i].clear();

		while(m--)

		{

			int u,v;	scanf("%d %d",&u,&v);

			G[u].push_back(v);

		}

		InitTar();

		for(j=0;j<n;j++)//可能图是不连通的，所以枚举所有未去过的点

			if(!vis[j])	tarjan(j);

	}

	return 0;

}
巴特西

强连通tarjan模版

最新文章

热门文章
