极大强连通分量Tarjan算法

[UNICKCHENG]

极大强连通分量Tarjan算法

带更新题库

[任务] 给定一个有向图,找出图中的极大强联通分量,并将属于同一个强联通分量内的点染同样的颜色
[说明]
dfn[i]记录的是节点i在深度优先遍历中的访问次序
low[i]记录的是点i可以到达的访问时间最早的祖先
Stack是记录节点的栈
深度优先遍历整个图,一路上标记dfn并把新节点压入栈中.对于一个节点i,如果它的dfn和low值相等,说明它无法到达它任何一个祖先.而在栈里面i与i之后的点一定是能够与i互达的(否则之前就会被弹出栈),所以i与栈里i之后的点形成一个极大强连通分量.这一部分可以作为整体弹出.
[接口]
struct strongly_connecterd_components
复杂度:O(|v|+|E|)

struct strongly_connecterd_components
{
	vector<int>&color;
	vector<int> Stack;
	int colorCnt,curr,*instack,*dfn,*low,*inf,*next,*to;

	vodi dfs(int x)
	{
		dfn[x]=low[x]=++cur;
		Stack.push_back(x);
		instack[x]=true;
		for(int j=info[x];j;j=next[j])
		{
			if(!instack[to[j]])
			{
				dfs(to[j]);
				low[x]=std:min(low[x],low[to[j]]);
			}
			else 
			{
				if(instack[to[j]]==1)low[x]=std:min(low[x],dfn[to[j]]);
			}
		}
		if(low[x]==dfn[x])
		{
			while(Stack.back()!=x)
			{
				color[Stack.back()]=colorCnt;
				instack[Stack.back()]=2;
				Stack.pop_back();
			}
			color[Stcak.back()]=colorCnt++;
			instack[Stack.back()]=2;
			Stack.pop_back();
		}
	}
	strongly_connecterd_components(const std::vector<std::pair<int,int>> &edgeList,int n,std::vector<int>&ans):color(ans)
	{
		color.resize(n);
		instack=new int[n];
		dfn=new int[n];
		low=new int[n];
		info=new int[n];
		next=new int[(int)edgeList.size()+5];
		to=new int[(int)edgeList.size()+5];
		std::fill_n(info,n,0);
		for(size_t i=0;i<edgeList.size();++i)
		{
			to[i+1]=edgeList[i].second;
			next[i+1]=info[edgeList[i].first];
			info[edgeList[i].first]=i+1;
		}
		std::fill_n(instack,n,0);
		colorCnt=0;
		curr=0;
		for(int i=0;i<n;i++)
			if(!instack[i]) dfs(i);
		delete[] instack;
		delete[] dfn;
		delete[] low;
		delete[] info;
		delete[] next;
		delete[] to;
	}
};

题库

ID	TITLE	CODE(C/C++)	备注
POJ2186	Popular Cows	查看代码