点双连通模版

白书上的所谓点连通模版似乎只有割点用用。。

binshen的板子：

int n, m;//n个点 m条无向边
#define N 20100
#define M 1000006
//点标从0开始
int head[N],edgenum;
int low[N], dfn[N], Stack[N<<1], top, instack[N],add_block[N],indexx,iscut[N], block_cnt; //block_cnt为图的连通分量数
struct Edge
{
	int from, to, next;
}edge[M<<1];
void add(int u,int v)
{
	Edge E = {u,v,head[u]};
	edge[edgenum] = E;
	head[u]=edgenum++;
}
void tarjin(int u,int pre)
{
	int i, v;
	low[u] = dfn[u] = ++indexx;
	Stack[top++] = u;
	int son = 0;
	for(i = head[u]; ~i; i = edge[i].next)
	{
		v = edge[i].to;
		if(v == pre)continue;
		if(!dfn[v])
		{
			son++;
			tarjin(v, u);
			if(low[u]>low[v])low[u]=low[v];
			if(u!=pre&&low[v]>=dfn[u])
			{
				iscut[u]=true;
				add_block[u]++;
			}
		}
		else if(low[u]>dfn[v])low[u]=dfn[v];
	}
	if(u==pre)add_block[u]=son-1;
	if(u==pre&&son>1)iscut[u]=true;
	//top--;
} 
void find_bcc(int n){
	memset(dfn, 0, sizeof(dfn));
	memset(instack, 0, sizeof(instack));
	memset(add_block, 0, sizeof(add_block));
	memset(iscut, 0, sizeof(iscut));
	indexx = top = 0;
	block_cnt = 0; //连通分量数
	for(int i = 0; i < n; i++)if(!dfn[i]) tarjin(i, i), block_cnt++;
}

板子2：

#define N 10010
struct Edge{
	int from, to, nex;
	bool cut;
}edge[100001*2];
int head[N], edgenum;
int bridgetop;
void addedge(int u, int v){
	Edge E={u,v,head[u],false};
	edge[ edgenum ] = E;
	head[u] = edgenum++;
}
int n, m;
int dfn[N], low[N], tarjan_time, tar, Stack[N], top;
int Belong[N];
bool iscut[N];
void tarjan(int u, int fa){
	dfn[u] = low[u] = ++tarjan_time;
	Stack[++top] = u;
	int child = 0, flag = 1;

	for(int i = head[u]; ~i; i = edge[i].nex)
	{
		int v = edge[i].to;
		if(flag && v==fa){flag = 0; continue;}
		if(!dfn[v])
		{
			child++;
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= dfn[u])
			{
				iscut[u] = true;

				if(low[v]>dfn[u])
					edge[i].cut = edge[i^1].cut = true;
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if(child == 1 && fa<0)iscut[u] = false;
	if(low[u] == dfn[u])
	{
		tar++;
		do
		{
			Belong[ Stack[top] ] = tar;
		}while(Stack[top--] != u);
	}
}

void init(){
	memset(head, -1, sizeof(head)), edgenum = 0;
	memset(dfn, 0, sizeof(dfn));
	memset(iscut, 0, sizeof(iscut));
	memset(Belong, -1, sizeof(Belong));
	bridgetop = 0;
	tarjan_time = 0;
	top = 0;
	tar = 0;
}

 

点双连通模版

原文：http://blog.csdn.net/acmmmm/article/details/18270383