无向图缩点：tarjan点双与边双缩点(模板)

const int N=1e4+100;
const int M=1e5+100;
struct Egde
{
	int to,next;
}edge1[M],edge2[M];
int head1[N],head2[N],low[N],dfn[N],c[N],num,cnt1,cnt2,dcc,n,m;
bool bridge[M];
void addedge1(int u,int v)
{
	edge1[cnt1].to=v;
	edge1[cnt1].next=head1[u];
	head1[u]=cnt1++;
}
void addedge2(int u,int v)
{
	edge2[cnt2].to=v;
	edge2[cnt2].next=head2[u];
	head2[u]=cnt2++;
}
void tarjan(int u,int in_edge)
{
	dfn[u]=low[u]=++num;
	for(int i=head1[u];i!=-1;i=edge1[i].next)
	{
		int v=edge1[i].to;
		if(!dfn[v])
		{
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
				bridge[i]=bridge[i^1]=true;
		}
		else if(i!=(in_edge^1))
			low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u)
{
	c[u]=dcc;
	for(int i=head1[u];i!=-1;i=edge1[i].next)
	{
		int v=edge1[i].to;
		if(c[v]||bridge[i])
			continue;
		dfs(v);
	}
}
void solve()
{
	for(int i=1;i<=n;i++)//找桥 
		if(!dfn[i])
			tarjan(i,0);
	for(int i=1;i<=n;i++)//缩点 
		if(!c[i])
		{
			dcc++;
			dfs(i);
		}
}
void build()//缩点+连边 
{
	solve();
	for(int i=2;i<cnt1;i+=2)
	{
		int u=edge1[i^1].to;
		int v=edge1[i].to;
		if(c[u]==c[v])
			continue;
		addedge2(c[u],c[v]);
		addedge2(c[v],c[u]);
	}
}
void init()
{
    cnt1=2;
	cnt2=num=dcc=0;
	memset(head2,-1,sizeof(head2));
	memset(head1,-1,sizeof(head1));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(bridge,false,sizeof(bridge));
	memset(c,0,sizeof(c));
}
v-DCC点双缩点：(用之前记得init)
const int N=1e4+100;
const int M=1e5+100;
struct Egde
{
	int to,next;
}edge1[M],edge2[M];
int head1[N],head2[N],low[N],dfn[N],c[N],Stack[N],new_id[N],num,cnt,cnt1,cnt2,tot,root,top,n,m;
bool cut[N];
vectordcc[N];
void addedge1(int u,int v)
{
	edge1[cnt1].to=v;
	edge1[cnt1].next=head1[u];
	head1[u]=cnt1++;
}
void addedge2(int u,int v)
{
	edge2[cnt2].to=v;
	edge2[cnt2].next=head2[u];
	head2[u]=cnt2++;
}
void tarjan(int u)
{
	dfn[u]=low[u]=++num;
	Stack[++top]=u;
	if(u==root&&head1[u]==-1)
	{
		dcc[++cnt].push_back(u);
		return;
	}
	int flag=0;
	for(int i=head1[u];i!=-1;i=edge1[i].next)
	{
		int v=edge1[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				flag++;
				if(u!=root||flag>1)
					cut[u]=true;
				cnt++;
				int x;
				do
				{
					x=Stack[top--];
					dcc[cnt].push_back(x);
				}while(x!=v);
				dcc[cnt].push_back(u);
			}
		}
		else
			low[u]=min(low[u],dfn[v]);
	}
}
void solve()
{
	for(int i=1;i<=n;i++)//找割点+缩点 
		if(!dfn[i])
		{
			root=i;
			tarjan(i);
		}
}
void build()//缩点+连边 
{
	solve();
	num=cnt1;
	for(int i=1;i<=n;i++)
		if(cut[i])
			new_id[i]=++num;
	for(int i=1;i<=cnt1;i++)
		for(int j=0;j<dcc[i].size();j++)
		{
			int x=dcc[i][j];
			if(cut[x])
			{
				addedge2(i,new_id[x]);
				addedge2(new_id[x],i);
			}
			else
				c[x]=i;
		}
}
void init()
{
	for(int i=0;i<N;i++)
		dcc[i].clear();
	cnt=cnt2=cnt1=num=tot=top=0;
	memset(head2,-1,sizeof(head2));
	memset(head1,-1,sizeof(head1));
	memset(low,0,sizeof(low));
	memset(dfn,0,sizeof(dfn));
	memset(cut,false,sizeof(cut));
	memset(c,0,sizeof(c));
	memset(Stack,0,sizeof(Stack));
	memset(new_id,0,sizeof(new_id));
}


作者：Frozen_Guardian
                    

 
                


                            tarjan
                            模板