可以求每個點屬于第幾個強連通分量：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 算法 常用模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。