强连通分支(scc)---tarjan

         本文大量参考：http://www.nocow.cn/index.php/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F

          感谢：byvoid

         首先，强连通分支是定义在一个有向图G上的。一个有向图的强连通分支就是一个最大的顶点集合，在这个集合中，所有的点都是互为可达的，即对于每一个点对（u,v）都能找到一条从u到v的通路，也都能找到一条从v到u的通路。对于一个有向图G,把G分解为各强连通分支是常用的操作，也有很多经典的算法。

        首先介绍kosaraju算法，这个算法描述起来比较简单，效率也很高。算法基于DFS，首先对于图G做一次DFS并且求出G的拓扑排序。然后，将G求转置（图G的转置就是将有向图中的边反向），得到GT。对于GT再做一次DFS，其中遍历的顺序要遵循所得到的拓扑排序。最后，对第二次的DFS形成的深度遍历森林，写出对于的强连通分支（森林中的每一颗树就是一个强连通分支）。分析一下效率，DFS对与邻接表O(V+E),求转置O(E)，因此，总的效率为O(V+E)

        接下来要重点介绍的是tarjan算法。tarjan基于一次DFS和一个栈空间，过程中引入2个参数low[],dfn[],dfn[i]表示的是G中点i是第几个被访问的。low[i]表示的是图中点i，在栈中所能追溯到的最远的先祖点j的dfn值。当算法回溯到点i,如果dfn[i]=low[i]，那么从栈顶到点i,就形成一个强连通分支。

   下面是算法流程：

   

tarjan(u)
{
	DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
	Stack.push(u)                              // 将节点u压入栈中
	for each (u, v) in E                       // 枚举每一条边
		if (v is not visted)               // 如果节点v未被访问过
			tarjan(v)                  // 继续向下找
			Low[u] = min(Low[u], Low[v])
		else if (v in S)                   // 如果节点v还在栈内
			Low[u] = min(Low[u], DFN[v])
	if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
		repeat
			v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
			print v
		until (u== v)
}

 值得注意的是low[i]的赋值，在dfs进入递归之前，线判断点j是否被访问，如果没有，就进入递归，递归回溯之后才开始给low[i]赋值，怎样赋值，取low[i]和low[j]中较小的一个。如果点i已经在栈中了，那不需要进入递归了，直接赋值。low[i]

取low[i]和dfn[j]中较小的一个（这里一只有个疑问，是否可以改成，low[i]=min(low[i],low[j])）。

      最后在回溯到点i之后，判断dfn[i]是否和low[i]相等，如果相等，做输出操作

下面是具体代码：

#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
class vertex
{
public:
	int t;
	vertex* next;
	vertex(int a):t(a)
	{
		this->next=NULL;
	}
	
};
const int maximum=200;
stack<int> s;
int index=0;
int dfn[maximum];
int low[maximum];
int state[maximum];//0:unvisited 1:instack 2:poped
int belog[maximum];
vertex* v[maximum];
void scc_tarjan(int i)
{
	int j;
	dfn[i]=low[i]=++index;
	state[i]=1;
	s.push(i);
	for(vertex *e=v[i]->next;e;e=e->next)
	{
		j=e->t;
		if(state[j]==0)
		{
			scc_tarjan(j);
			if(low[j]<low[i])
				low[i]=low[j];
		}
		else if(state[j]==1&&dfn[j]<low[i])
			low[i]=dfn[j];
	}
	if(dfn[i]==low[i])
	{
		int a=-1;
		while(a!=i)
		{
			a=s.top();
			s.pop();
			state[a]=2;
			belog[a]=i;	
		}
		belog[i]=i;
			
	}

}
void init()
{
	for(int i=1;i<=6;i++)
	{
		vertex*s=new vertex(i);
		v[i]=s;
	}
	v[1]->next=new vertex(3);
	v[1]->next->next=new vertex(2);
	v[2]->next=new vertex(4);
	v[3]->next=new vertex(5);
	v[3]->next->next=new vertex(4);
	v[4]->next=new vertex(6);
	v[4]->next->next=new vertex(1);
	v[5]->next=new vertex(6);
	/*for(int i=1;i<=8;i++)
	{
		vertex*s=new vertex(i);
		v[i]=s;
	}
	v[1]->next=new vertex(4);
	v[2]->next=new vertex(1);
	v[2]->next->next=new vertex(5);
	v[3]->next=new vertex(2);
	v[4]->next=new vertex(2);
	v[5]->next=new vertex(4);
	v[6]->next=new vertex(3);
	v[6]->next->next=new vertex(5);
	v[7]->next=new vertex(6);
	v[7]->next->next=new vertex(8);
	v[8]->next=new vertex(6);
	v[8]->next->next=new vertex(7);
	*/
}
int main()
{
	memset(state,0,sizeof(state));
	memset(v,0,sizeof(v));
	index=0;
	while(!s.empty())
	{
		s.pop();
	}
	init();
	for(int i=1;i<=6;i++)
	{
		if(state[i]==0)
			scc_tarjan(i);
	}
	for(int i=1;i<=6;i++)
	{
		cout<<i<<" is belog to "<<belog[i]<<endl;
	}
}