学步园

无向图的割顶，桥和构造双连通分量以及有向图的极大连通分量，相关概念看这里 http://www.byvoid.com/blog/biconnect/

程序部分自己写，理论部分参考上方链接。

根据黑书上面的相关内容，无向图的tarjan算法大致如下:

/*
 * 注释1：去除注释1即为无向图求割顶的算法。
 * 		  特别的，若最终 sons>1，则节点1也为一个割点。
 * 		  调用时 tarjan(1,0);
 * 注释2：去除注释2即为无向图求桥的算法。
 * 		  bridge[i]为真表示边的邻接表中的第i条边为桥。
 * 		  调用时 tarjan(1,0);
 * low[]的编号即为连通分量的编号。
 * */
void tarjan(int x,int father)
{
	int i,j;
	dfn[x] = low[x] = ++index;
	for(i=head[x];i;i=edge[i].next)
	{
		j = edge[i].v;
		if(j!=father)	//这个判断不要忽略了,特别在无向图中很重要。
		{
			if(!dfn[j])
			{
		//1		if(x==1) sons++;
				tarjan(j,x);
				low[x] = min(low[x],low[j]);
		//1		if(x!=1 && low[j]>=dfn[x]) cut[x] = true;
		//2		if(low[j]>dfn[x]) bridge[i] = true;
			}else
				low[x] = min(low[x],dfn[j]);
		}
	}
	return;
}

若要求构造双连通分量，则要利用LCA算法，还是Tarjan的成果。参见上方链接。

有向图的tarjan算法，求极大连通分量

/*
 * 有向图的tarjan算法，求极大连通分量。
 * 与无向图相比，去掉 j!=father 的判断。
 * 另外，low[]的编号不能表示连通分量的编号，
 *     而必须用栈来对结点进行编号。
 * 调用时，由于有多个连通分量，一次dfs无法全部遍历，
 * 	   所以：
 * 	   for(i=1;i<=n;i++)
 * 	   	   if(!dfn[i])
 * 	   	       tarjan(i);
 * */
void tarjan(int x)
{
	int i,j;
	dfn[x] = low[x] = ++index;
	for(i=head[x];i;i=edge[i].next)
	{
		j = edge[i].v;
		//if(j!=father)	
		//{
			if(!dfn[j])
			{
				tarjan(j,x);
				low[x] = min(low[x],low[j]);
			}else
				low[x] = min(low[x],dfn[j]);
		//}
	}
	
	if(low[x]==dfn[x])
	{
		label++;
		do
		{
			j = stack[deep--];
			lab[j] = label;
		}while(j!=x);
	}
	return;
}