tarjan模板 强联通分量+割点+割边

// https://www.cnblogs.com/stxy-ferryman/p/7779347.html const int N=1005; struct EDGE { int to, nt; }e[N*N]; int head[N], tot; void addE(int u,int v) { e[tot].to=v; e[tot].nt=head[u]; head[u]=tot++; } int dfn[N], low[N], ind; int col[N], id; bool vis[N]; stack <int> s; void init() { while(!s.empty()) s.pop(); for(int i=0;i<=n;i++) { head[i]=dfn[i]=low[i]=col[i]=-1; vis[i]=du[i]=0; } tot=ind=id=0; } // 求强联通分量 并将各个分量染色为1~id void tarjan(int u) { dfn[u]=low[u]=ind++; s.push(u); vis[u]=1; for(int i=head[u];i!=-1;i=e[i].nt) { int v=e[i].to; if(dfn[v]==-1) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],low[v]); } if(dfn[u]==low[u]) { col[u]=++id; vis[u]=0; while(s.top()!=u) { col[s.top()]=id; vis[s.top()]=0; s.pop(); } s.pop(); } } // 求割点 若i是割点 iscut[i]=1 int tarjanN(int u,int fa) { int son=0, lowu; dfn[u]=lowu=ind++; for(int i=head[u];i!=-1;i=e[i].nt) { int v=e[i].to; if(dfn[v]==-1) { son++; int lowv=tarjan(v,u); lowu=min(lowu,lowv); if(lowv>dfn[u]) iscut[u]=1; } else if(v!=fa && dfn[v]<dfn[u]) low[u]=min(low[u],low[v]); } if(fa<0 && son==1) iscut[u]=0; return low[u]=lowu; } // 求割边 边的信息存入E vector < pair<int,int> > E; int tarjanE(int u,int fa) { int lowu; dfn[u]=lowu=ind++; for(int i=head[u];i!=-1;i=e[i].nt) { int v=e[i].to; if(dfn[v]==-1) { int lowv=tarjan(v,u); lowu=min(lowu,lowv); if(lowv>dfn[u]) { int from=u, to=v; if(from>to) swap(from,to); E.push_back(make_pair(from,to)); } } else if(v!=fa && dfn[v]<dfn[u]) low[u]=min(low[u],low[v]); } return low[u]=lowu; }

 

转载于:https://www.cnblogs.com/zquzjx/p/10020938.html