有向图缩点：tarjan强连通缩点(模板)

SCC强连通缩点：(用之前记得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],num,cnt,cnt2,cnt1,dcc,n,m,top;

bool ins[N];

vectorscc[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; ins[u]=true; 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]); } else if(ins[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { cnt++; int v; do { v=Stack[top--]; ins[v]=false; c[v]=cnt; scc[cnt].push_back(v); }while(u!=v); } }

void solve() { for(int i=1;i<=n;i++)//缩点 if(!dfn[i]) tarjan(i); }

void build()//缩点+连边 { solve(); for(int i=1;i<=n;i++) { for(int j=head1[i];j!=-1;j=edge1[j].next) { int u=i; int v=edge1[j].to; if(c[u]!=c[v]) addedge2(c[u],c[v]); } } }

void init() { for(int i=0;i<N;i++) scc[i].clear(); top=cnt=cnt1=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(c,0,sizeof(c)); memset(ins,false,sizeof(ins)); }

作者：Frozen_Guardian

有向图缩点 tarjan 模板 有向图