本次專題是強(qiáng)連通分量的tarjan算法，以下程序包含stl建圖，dfs遍歷，強(qiáng)連通分量假縮點(diǎn)，求縮點(diǎn)入度出度。
#include<iostream>#include<cstdio>#include<stack>#include<vector>#include<cmath>#define M 10005using namespace std;stack<int>S;int PRe[M],//dfs的步數(shù)（時(shí)間） low[M],//若屬于同一強(qiáng)連通分量，則Low值更改為之前的最小時(shí)間； c[M],k[M], belong[M],//記錄是否屬于同一強(qiáng)連通分量 in[M],//分量入度 out[M];//分量出度int m,n,time1,time2,t1,t2,w;vector<int>g[M];void dfs(int u){ pre[u]=low[u]=time1++;//步數(shù)＋1 S.push(u);//當(dāng)前節(jié)點(diǎn)出棧 for(int i=0;i<g[u].size();i++)//遍歷當(dāng)前節(jié)點(diǎn)所連結(jié)點(diǎn) { int v=g[u][i]; if(!pre[v])//若未被遍歷 { dfs(v); low[u]=min(low[u],low[v]);//low值更改 } if(!c[v]) low[u]=min(pre[v],low[u]); } if(pre[u]==low[u])//若當(dāng)前節(jié)點(diǎn)步數(shù)值等于low值，則一個(gè)強(qiáng)連通分量構(gòu)成 { time2++;//分量數(shù)+1 while(1) { int x=S.top();S.pop();//出棧 c[x]=time2; belong[x]=time2; if(x==u)break; } }}void find(){ for(int i=1;i<=n;i++) if(!pre[i])dfs(i);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { while(1) { scanf("%d",&t1); if(t1==0)break; g[i].push_back(t1); } } find(); for(int i=1;i<=n;i++) for(int j=0;j<g[i].size();j++) { int v=g[i][j]; if(belong[i]!=belong[v])//若不屬于同一強(qiáng)連通分量 { in[belong[v]]++;//下一分量入度加1 out[belong[i]]++;//當(dāng)前分量出度加1 } } //以下過(guò)程針對(duì) 洛谷P2812 /*int ans1=0,ans2=0; for(int i=1;i<=time2;i++) { if(in[i]==0) ans1++; if(out[i]==0) ans2++; } if(time2==1) { printf("1/n0"); return 0; } ans2=max(ans1,ans2); printf("%d/n%d",ans1,ans2);*/ return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
