图论算法-Tarjan模板 【缩点;割顶;双连通分量】
图论算法-Tarjan模板 【缩点;割顶;双连通分量】
为小伙伴们总结的Tarjan三大算法
Tarjan缩点(求强连通分量)
int n; int low[100010],dfn[100010]; bool ins[100010]; int col[100010];//记录每个点所属强连通分量(即染色) vector<int> map[100010]; stack<int> st; int tot;//时间戳 int colnum;//记录强连通分量个数 void tarjan(int u) { low[u]=dfn[u]=++tot; st.push(u); ins[u]=true; for(int j=0;j<map[u].size();j++) { int v=map[u][j]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(ins[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { //到这里即发现了一个新的强连通分量 colnum++; int temp; int cont=0; do { temp=st.top(); st.pop(); ins[temp]=false; //将同一强连通分量的点染色,表示一个缩点 col[temp]=colnum; //在这里也可以对该强连通分量进行一些其他操作 //例如保存该缩点所包含的原节点 } while(temp!=u); } } void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(col,0,sizeof(col)); memset(ins,false,sizeof(ins)); tot=colnum=0; } void solve() { init(); for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } }
Tarjan求割点(割顶)
int n; vector<int> map[100010]; int low[100010],dfn[100010]; bool cut[1000010];//记录割点 int tot; void tarjan(int u,int fa) { low[u]=dfn[u]=++tot; int child=0; for(int j=0;j<map[u].size();j++) { int v=map[u][j]; if(!dfn[v]) { child++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) cut[u]=true; } else if(dfn[v]<dfn[u]&&v!=fa) low[u]=min(low[u],dfn[v]); } if(fa<0&&child==1) cut[u]=false; } void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(cut,false,sizeof(cut)); tot=0; } void solve() { init(); for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i,-1); //**高亮**这里的第二个参数一定要设为负数 } //cut[i]==true即表示i为割点 }
Tarjan求点-双连通分量
int n; vector<int> map[100010]; int low[100010],dfn[100010]; bool cut[1000010]; int bcc[1000010]; int tot; int bcc_cont//记录双连通分量个数; struct edge{int u,v}; stack<edge> E; void tarjan(int u,int fa) { low[u]=dfn[u]=++tot; int child=0; for(int j=0;j<map[u].size();j++) { int v=map[u][j]; edge e=(edge) {u,v}; if(!dfn[v]) { E.push(e); child++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]) { //到这里即发现了一个新的双连通分量 cut[u]=true; bcc_cont++: while(1) { edge temp=E.top(); E.pop(); if(bccno[temp.u]!=bcc_cont) bccno[temp.u]=bcc_cont; if(bccno[temp.v]!=bcc_cont) bccno[temp.v]=bcc_cont; if(temp.u==u&&temp.v==v) break; } } } else if(dfn[v]<dfn[u]&&v!=fa) { E.push(e); low[u]=min(low[u],dfn[v]); } } if(fa<0&&child==1) cut[u]=false; } void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(bccno,0,sizeof(bccno)); tot=bcc_cont=0; } void solve() { init(); for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i,-1);//**高亮**这里的第二个参数一定要设为负数 } }
其实三个算法思路都基本一致
毕竟都是同一个人提出的嘛