變量解釋：
low 指當前節點在同一強連通分量（或環）能回溯到的dfn最小的節點
dfn 指當前節點是第幾個被搜到的節點（時間戳）
sta 棧
vis 是否在棧中
ans 指強連通分量的數量
top 棧頂

1.求強連通分量
定義：如果兩個頂點可以相互通達，則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。

算法：在有向圖中從一點（u）開始dfs，記錄dfn，搜到一個已在棧中的點（v）時用dfn[v] (low[v]也行，但只有求強連通分量時可以別的只能用dfn[v]) 嘗試更新low[u]，并在回溯時更新沿路的點的low值，走到low值與dfn相同的點時記錄這個強連通分量即可。
也就是說：在同一個強連通分量中所有點low值相同，也就是有一個代表點（代表點即所有點的low值即強連通分量中dfn值最小的點）
時間復雜度為O(E+V)

code

void tarjan(int u){dfn[u]=low[u]=++cnt;//初始化一點的dfn和lowsta[++top]=u,vis[u]=true;//入棧for(int i=head[u];i;i=edge[i].next){//鄰接表int v=edge[i].to;if(!dfn[v]){//如果沒走過tarjan(v);low[u]=min(low[u],low[v]);//回溯過程時low值傳遞}else if(vis[v]) low[u]=min(low[u],dfn[v]); //low[v]也行 用代表點更新}if(dfn[u]==low[u]) {//如果是代表點 記錄并出棧ans++;//記錄強連通分量個數while(sta[top]!=u){vis[sta[top]]=false;top--;}vis[sta[top]]=false;top--;}return ; }

2.求無向圖的割點與割邊
割點：在無向圖中，如果將一個點以及所有連接該點的邊都去掉，圖就不再連通，那么這個點就叫做這個圖的一個割點。
割邊：在無向圖中，如果將一條邊去掉，圖就不再連通則稱這條邊為圖的一個割邊。

求割點：如果一個點（u）所連接的幾個節點（v）的low值大或等于此節點（u）的dfn值時說明之后的節點（v）無法連接到比此點（u）更早的點上，則說明這個節點（u）是一個割點。PS：根節點需特判，當根節點在dfs樹有兩個或更多個子樹時則說明根節點是割點

求割邊：與割點類似，如果一個點（u）的dfn值大于（不能等于，否則不一定）和它連接的一個節點（v）的low值，則說明這條邊（uv）為圖的一個割邊

變量解釋：
sum 指總共有幾個割點（邊）

割點code

void cutpoint(int u){int fl=0;//為特判準備dfn[u]=low[u]=++cnt;//初始化for(int i=head[u];i;i=edge[i].next){//用鄰接表，下同int v=edge[i].to;if(!dfn[v]){cutpoint(v);low[u]=min(low[u],low[v]);if(u!=root&&low[v]>=dfn[u]&&!cpoint[u]) sum++,cpoint[u]=1;//不是根節點&&v的low值>=u的dfn值&&此點沒有算過if(u==root) fl++;//此時特判++}low[u]=min(low[u],dfn[v]); }if(fl>=2&&!cpoint[u]) sum++,cpoint[u]=1;//根節點若有兩棵子樹則是割點 }

割邊code

void cutedge(int u,int f){dfn[u]=low[u]=++cnt;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){cutedge(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]) cedge[++sum]=i;//記錄邊的序號}else if(v!=f) low[u]=min(low[u],dfn[v]); //只有當v不是u的上一個節點時可行} }

完整模板code:
ps：這里就不打注釋了，核心就在上面的部分里

#include<cstdio> #include<iostream> #include<cstring> using namespace std;const int MAX=1000010; int n,m,cnt,sum,root; int head[MAX],low[MAX],dfn[MAX],cpoint[MAX],cedge[MAX];struct edg{int to,next,from; }edge[MAX];void add(int x,int y){edge[++cnt].next=head[x];edge[cnt].from=x,edge[cnt].to=y;head[x]=cnt; }void cutpoint(int u){int fl=0;dfn[u]=low[u]=++cnt;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){cutpoint(v);low[u]=min(low[u],low[v]);if(u!=root&&low[v]>=dfn[u]&&!cpoint[u]) sum++,cpoint[u]=1;if(u==root) fl++;}low[u]=min(low[u],dfn[v]); }if(fl>=2&&!cpoint[u]) sum++,cpoint[u]=1; }void cutedge(int u,int f){dfn[u]=low[u]=++cnt;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(!dfn[v]){cutedge(v,u);low[u]=min(low[u],low[v]);if(dfn[u]<low[v]) cedge[++sum]=i;}else if(v!=f) low[u]=min(low[u],dfn[v]);} }void mset(){memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);cnt=sum=0; }void find_cutpoint(){for(int i=1;i<=n;i++) if(!dfn[i]) {root=i;cutpoint(i);}printf("%d\n",sum);for(int i=1;i<=n;i++) if(cpoint[i]) printf("%d ",i); }void find_cutedge(){for(int i=1;i<=n;i++) if(!dfn[i]) cutedge(i,0);printf("%d\n",sum);for(int i=1;i<=sum;i++) printf("%d %d\n",edge[cedge[i]].from,edge[cedge[i]].to); }int main(){ // freopen("testdata.txt","r",stdin);scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){int a,b;scanf("%d %d",&a,&b);add(a,b);add(b,a);}find_cutedge();mset();find_cutpoint();return 0; }

轉載于:https://www.cnblogs.com/Menteur-Hxy/p/9248051.html

總結

以上是生活随笔為你收集整理的Tarjan算法 （强联通分量 割点 割边）的全部內容，希望文章能夠幫你解決所遇到的問題。

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