tarjan强连通分量模板

#include<bits/stdc++.h>
using namespace std;
vector<int>edge[MAXN],scc[MAXN];
int n,m;
int dfn[MAXN],low[MAXN],cnt,cc,in[MAXN],id[MAXN];
stack<int>s;
void tarjan(int u)
{
	low[u]=dfn[u]=++cnt;
	s.push(u);
	in[u]=1;
	for(int i=0;i<edge[u].size();i++)
	{
		int x=edge[u][i];
		if(!dfn[x])
		{
			tarjan(x);
			low[u]=min(low[u],low[x]);
		}
		else if(in[x]) low[u]=min(low[u],dfn[x]);
	}
	if(dfn[u]==low[u])
	{
		int p;
		cc++;
		do{
			p=s.top();
			s.pop();
			in[p]=0;
			id[p]=cc;
			scc[cc].push_back(p);
			
		}while(u!=p);
		
	}
}

  1. id[x] x所属强连通分量的编号
  2. scc[i] 编号为i的强连通分量中所有节点
  3. cnt 强连通分量个数
  4. in[x] x是否在栈中

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注