愛在心中?vijos-1626 jdoj-1588

　　　　題目大意：給你n個點和m條有向邊，求出大于一的強連通分量的個數(shù)以及是否存在唯一的強連通分量使得這個分量可以被任意點到達。如果存在，則排序輸出這個強聯(lián)通分量里的點，如果不存在或大于1個，則輸出-1。

　　　　注釋：n<=1000，m<=10000

　　　　　　想法：咳咳，又是一個新知識點，別問我博主為什么最近狂學(xué)知識點...就因為一個LCA啊！(其實是受刺激了)。好，我們今天來說一下tarjan算法。所謂tarjan，就是在多項式時間復(fù)雜度內(nèi)求出強連通分量的算法。顯然，這題是一道裸題(這題的題目描述不是這樣的啊？！炒雞惡心的)。我在這里簡略的說一下tarjan算法。

　　　　　　　　我們用deep數(shù)組和low數(shù)組來記錄，其中，low數(shù)組表示時間戳，deep數(shù)組表示第幾個被搜到。然后，我們tarjan的過程就是dfs。對于一個剛剛被搜到的節(jié)點i，我把它扔進棧里，緊接著我來枚舉這個點的出邊。如果枚舉到了一個棧里的點，證明那個棧里的點可以聯(lián)通到i且i有一條邊聯(lián)想棧中節(jié)點。所以，i和棧里的點在同一個強聯(lián)通分量里。那么，我們怎么記錄呢？我們用時間戳來記錄。顯然這個時候，i到那個棧里的點之間的點都可以通過i連向棧里的點的邊相互聯(lián)通，所以，他們之間的點的都隸屬于同一個強聯(lián)通分量里。那么，我們就用那個棧里的最開始與i聯(lián)通的點為這個強聯(lián)通分量的標(biāo)志。但是，我們將i連向的點與i當(dāng)做同一個強聯(lián)通分量當(dāng)且僅當(dāng)我們已經(jīng)枚舉完i的所有出邊，即可。最后，我們用f[i]來表示一個強連通分量里的所有點，其中f[i][0]表示這個強聯(lián)通分量里面點的個數(shù)。

　　　　最后，我們來理解一下這個好看的版子(鳴謝panxf老師)... ...

void tarjan(int x) {z[++top]=x;v[x]=1;inz[x]=1;// v[ ] 表示是否被處理過，inz[ ]表示是否在棧中。deep[x]=low[x]=++tot; //deep[ ],low[ ],如上所述。for(int i=1;i<=n;i++) //枚舉鄰接矩陣中的x的每一條出邊。if(a[x][i]==1){if(v[i]==0) tarjan(i),low[x]=min(low[x],low[i]); //沒有被訪問過，更新low[x]else if(inz[i]==1) low[x]=min(low[x],deep[i]); //如果在棧中，更新low[x] ????????}if(deep[x]==low[x]) //當(dāng)x的出邊都處理過后，如果deep[x]==low[x] ????{ ans++; //記錄最大連通分量的個數(shù)。int t; //t記錄棧頂元素 do //do{ }while(); 先執(zhí)行再判斷。 ????????{t=z[top--],inz[t]=0; //取出棧頂 f[ans][++f[ans][0]]=t; //記錄最大連通分量的集合元素。}while(t!=x);} }

　　　　然后，我們來說明一下這道題。我們發(fā)現(xiàn)第一問統(tǒng)計答案顯然是簡單的，我們來看一下第二問。我們先將每一個強聯(lián)通分量縮成一個大的點，每一個所隸屬的強連通分量我們用inwhat來表示，所以，最后的強連通分量的個數(shù)不是anss，而是ans。然后，我們暴力枚舉所有的邊，來枚舉縮完點之后的這個圖的情況。緊接著，我們來證明一個事情：如果一個點是在這道題中滿足題意者，那么它所必須要滿足的條件是出度為0且這張圖中只有這一個強聯(lián)通分量的出度為0。為什么？我們來嘗試證明：

　　　　首先，如果這個點的出度不是0且滿足題意：我們假設(shè)這個點是a，有一條出邊指向了b。那么此時，如果a滿足題意，則所有的點又可以指向或間接指向a，又因為a指向b，所以所有點有除了a的點都可以先指向a再指向b，且a直接指向b，所以，b也滿足題意，與題中只有一個點滿足題意矛盾，所以，一個點滿足題意必要條件是這個點的出度是0。

　　　　其次，我們來證明如果存在多個點出度是0也不滿足題意。對于這樣的兩個點a和b，出度都是0。仍然采用反證法：如果a滿足題意，那么b指向a，但是b并沒有任何出邊，所以b不可能指向任何點，所以b不可能指向或間接指向a，所以，矛盾。故此，證畢。

　　　　此時，顯然我們可以直接枚舉所有的強連通分量，以至于特判和輸出即可。

　　　　最后，附上丑陋的代碼... ...

1 #include <iostream> 2 #include <cstdio> 3 // #include <cstring> 4 #include <algorithm> 5 #define N 1010 6 using namespace std; 7 int z[N],top,deep[N],low[N],tot,ans,a[N][N],f[N][N]; 8 int inwhat[N]; 9 int chu[N]; 10 int x[N],y[N]; 11 bool v[N],inz[N]; 12 bool isv[N]; 13 int n; 14 void tarjan(int x) 15 { 16 z[++top]=x;v[x]=inz[x]=1; 17 deep[x]=low[x]=++tot; 18 for(int i=1;i<=n;i++) 19 { 20 if(a[x][i]) 21 { 22 if(!v[i]) tarjan(i),low[x]=min(low[x],low[i]); 23 else if(inz[i]) low[x]=min(low[x],deep[i]); 24 } 25 } 26 if(deep[x]==low[x]) 27 { 28 ans++; 29 int t; 30 do{ 31 t=z[top--],inz[t]=0; 32 f[ans][++f[ans][0]]=t; 33 inwhat[t]=ans; 34 }while(t!=x); 35 } 36 } 37 int main() 38 { 39 int m; 40 scanf("%d%d",&n,&m); 41 for(int i=1;i<=m;i++) 42 { 43 scanf("%d%d",&x[i],&y[i]); 44 a[x[i]][y[i]]=1; 45 //a[y][x]=1; 46 isv[x[i]]=1;//表示x[i]這個點有出邊 47 } 48 for(int i=1;i<=n;i++) 49 { 50 if(isv[i]&&!v[i])//這樣可以使得遍歷整個圖 51 { 52 tarjan(i); 53 } 54 } 55 int anss=0; 56 for(int i=1;i<=ans;i++)//這是第一問，f[i][0]表示第i個強連通分量的點的個數(shù) 57 { 58 if(f[i][0]!=1) anss++; 59 } 60 printf("%d\n",anss); 61 for(int i=1;i<=m;i++) 62 { 63 if(inwhat[x[i]]!=inwhat[y[i]]) 64 chu[inwhat[x[i]]]++;//這步很重要，我們計算一個強連通分量的出邊是不可以計算強聯(lián)通分量之內(nèi)的邊 65 } 66 /*for(int i=1;i<=ans;i++) 67 { 68 for(int j=1;j<=f[i][0];j++) 69 { 70 printf("%d ",f[i][j]); 71 } 72 puts(""); 73 } 74 for(int i=1;i<=ans;i++) printf("chu[%d]=%d\n",i,chu[i]);*/ 75 int cnt=0;//記錄有多少出度為0的邊。 76 int count=1;//記錄出度為0的邊是幾。 77 for(int i=1;i<=ans;i++) 78 { 79 if(chu[i]==0) cnt++,count=i; 80 } 81 if(cnt>1) printf("-1\n"); 82 else 83 { 84 if(f[count][0]==1)//如果只有一個點，是不滿足題意的 85 { 86 printf("-1"); 87 return 0; 88 } 89 sort(f[count]+1,f[count]+f[count][0]+1);//排序 90 for(int i=1;i<=f[count][0];i++) printf("%d ",f[count][i]); 91 } 92 return 0; 93 }

　　　　小結(jié)：tarjan可以解決很多問題，也是一種遍歷的思想，在處理LCA是比較實用。

　　　　　　錯誤：1.枚舉強連通分量的出度是不要枚舉強連通分量之內(nèi)的邊的情況。

　　　　　　　　　2.題目中的描述是解題的關(guān)鍵。

　　　　　　　　　3.開始想的是floyd，結(jié)果發(fā)現(xiàn)過不去，告訴我們做題要注意數(shù)據(jù)范圍。

轉(zhuǎn)載于:https://www.cnblogs.com/ShuraK/p/8305872.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的爱在心中的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。