Tarjan 算法 常用模板

可以求每个点属于第几个强连通分量：https://blog.csdn.net/dellaserss/article/details/8267192

int Tarjan(int u){int v;dfn[u]=low[u]=++Index;stack[++Top]=u;Instack[u]=1;for(int i=0;i<G[u].size();i++){v=G[u][i];if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(Instack[v]) low[u]=min(dfn[v],low[u]);}if(dfn[u]==low[u]){CNT++;do{v=stack[Top--];Belong[v]=CNT;Instack[v]=0;}while(u!=v);} }

可以求强连通分量的个数：

void tarjan(int x) {low[x] = dfn[x] = ++tot;sk.push(x);vis[x] = 1;for(int i = head[x]; i!=-1; i=e[i].ne) {int v = e[i].to;if(dfn[v] == 0) {tarjan(v);low[x] = min(low[x],low[v]);}else if(vis[v] == 1) {low[x] = min(low[x],dfn[v]);}}if(low[x] == dfn[x]) {cnt++;while(1) {int now = sk.top();sk.pop();vis[now]=0;if(now == x) break;}} }

可以求强连通分量中的点分别是谁：https://blog.csdn.net/qq_34374664/article/details/77488976

void tarjan(int x)//代表第几个点在处理。递归的是点。{DFN[x]=LOW[x]=++tot;// 新进点的初始化。stack[++index]=x;//进站visit[x]=1;//表示在栈里for(int i=heads[x];i!=-1;i=edge[i].next){if(!DFN[edge[i].v]) {//如果没访问过tarjan(edge[i].v);//往下进行延伸，开始递归LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。}else if(visit[edge[i].v ]){ //如果访问过，并且还在栈里。LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系}}if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。{do{printf("%d ",stack[index]);visit[stack[index]]=0;index--;}while(x!=stack[index+1]);//出栈，并且输出。printf("\n");}return ;}

编辑时间回忆：

总结

以上是生活随笔为你收集整理的Tarjan 算法 常用模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。