縮點常應用于給一個有向圖，求在圖中最少要加多少條邊能使得該圖變成一個強連通圖

首先求出該圖的各個強連通分量，然后把每個強連通分量看出一個點(即縮點)，最后得到了一個有向無環(huán)圖(DAG)

對于一個DAG，需要添加 max(a,b) 條邊才能使其強連通

其中 a 為 DAG 中出度為 0 的點總數，b 為 DAG 中入度為 0 的點總數

int n,m; vector<int> G[N]; stack<int> S; int dfn[N],low[N]; bool vis[N];//標記數組 int sccno[N];//記錄結點i屬于哪個強連通分量 bool in[N],out[N];//記錄入度、出度是否為0 int block_cnt;//時間戳 int sig;//記錄強連通分量個數 void Tarjan(int x){vis[x]=true;dfn[x]=low[x]=++block_cnt;//每找到一個新點，紀錄當前節(jié)點的時間戳S.push(x);//當前結點入棧for(int i=0;i<G[x].size();i++){//遍歷整個棧int y=G[x][i];//當前結點的下一結點if(vis[y]==false){//若未被訪問過Tarjan(y);low[x]=min(low[x],low[y]);}else if(!sccno[y])//若已被訪問過，且不屬于任何一個連通分量low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){//滿足強連通分量要求sig++;//記錄強連通分量個數while(true){//記錄元素屬于第幾個強連通分量int temp=S.top();S.pop();sccno[temp]=sig;if(temp==x)break;}} } void shrink(){//縮點memset(in,false,sizeof(in));memset(out,false,sizeof(out));for(int i=1;i<=sig;i++){//對于所有的強連通分量，將其入度、出度均視為1in[i]=true;out[i]=true;}for(int x=0;x<n;x++){//枚舉n個點for(int i=0;i<G[x].size();i++){//對第x個點的每個后繼節(jié)點int y=G[x][i];if(sccno[x]!=sccno[y]){//統(tǒng)計每個點出度、入度是否為0out[sccno[x]]=false;in[sccno[y]]=false;}}} } int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)G[i].clear();while(m--){int x,y;scanf("%d%d",&x,&y);x--;y--;G[x].push_back(y);}sig=0;block_cnt=0;memset(vis,false,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(sccno,0,sizeof(sccno));//Tarjan求強連通分量for(int i=0;i<n;i++)if(vis[i]==false)Tarjan(i);shrink();//縮點int a=0,b=0;for(int i=1;i<=sig;i++){//統(tǒng)計入度、出度為0的點的個數if(in[i])a++;if(out[i])b++;}int res=max(a,b);if(sig==1)//強連通分量為1時res=0;printf("%d\n",res);} }

總結

以上是生活随笔為你收集整理的图论 —— 图的连通性 —— Tarjan 缩点的全部內容，希望文章能夠幫你解決所遇到的問題。

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