校園網絡
時間限制： 3000 ms | 記憶體限制： 65535 KB 難度： 5
- 描述
-
南陽理工學院共有M個系，分别編号1~M,其中各個系之間達成有一定的協定，如果某系有新軟體可用時，該系将允許一些其它的系複制并使用該軟體。但該允許關系是單向的，即：A系允許B系使用A的軟體時，B未必一定允許A使用B的軟體。
現在，請你寫一個程式，根據各個系之間達成的協定情況，計算出最少需要添加多少個兩系之間的這種允許關系，才能使任何一個系有軟體使用的時候，其它所有系也都有軟體可用。
- 輸入
-
第一行輸入一個整數T，表示測試資料的組數(T<10)
每組測試資料的第一行是一個整數M，表示共有M個系(2<=M<=100)。
随後的M行，每行都有一些整數，其中的第i行表示系i允許這幾個系複制并使用系i的軟體。每行結尾都是一個0，表示本行輸入結束。如果某個系不允許其它任何系使用該系軟體，則本行隻有一個0.
輸出 - 對于每組測試資料，輸出最少需要添加的這種允許關系的個數。 樣例輸入
-
1 5 2 4 3 0 4 5 0 0 0 1 0 樣例輸出 -
2 來源 - POJ改編
- 解析（轉）：
- Tarjan算法詳解
-
【功能】
Tarjan算法的用途之一是，求一個有向圖G=(V,E)裡極大強連通分量。強連通分量是指有向圖G裡頂點間能互相到達的子圖。而如果一個強連通分量已經沒有被其它強通分量完全包含的話，那麼這個強連通分量就是極大強連通分量。
【算法思想】
用dfs周遊G中的每個頂點，通dfn[i]表示dfs時達到頂點i的時間，low[i]表示i所能直接或間接達到時間最小的頂點。(實際操作中low[i]不一定最小，但不會影響程式的最終結果)
程式開始時，order初始化為0，在dfs周遊到v時，low[v]=dfn[v]=order++，
v入棧（這裡的棧不是dfs的遞歸時系統弄出來的棧）掃描一遍v所能直接達到的頂點k，如果 k沒有被通路過那麼先dfs周遊k，low[v]=min(low[v],low[k])；如果k在棧裡，那麼low[v]=min(low[v],dfn[k])(就是這裡使得low[v]不一定最小，但不會影響到這裡的low[v]會小于dfn[v])。掃描完所有的k以後，如果low[v]=dfn[v]時，棧裡v以及v以上的頂點全部出棧，且剛剛出棧的就是一個極大強連通分量。
【大概的證明】
1． 在棧裡，當dfs周遊到v，而且已經周遊完v所能直接到達的頂點時，low[v]=dfn[v]時，v一定能到達棧裡v上面的頂點：
因為當dfs周遊到v，而且已經dfs遞歸調用完v所能直接到達的頂點時（假設上面沒有low=dfn），這時如果發現low[v]=dfn[v]，棧上面的頂點一定是剛才從頂點v遞歸調用時進棧的，是以v一定能夠到達那些頂點。
2 .dfs周遊時，如果已經周遊完v所能直接到達的頂點而low[v]=dfn[v]，我們知道v一定能到達棧裡v上面的頂點，這些頂點的low一定小于 自己的dfn，不然就會出棧了，也不會小于dfn[v],不然low [v]一定小于dfn[v],是以棧裡v以其v以上的頂點組成的子圖是一個強連通分量，如果它不是極大強連通分量的話low[v]也一定小于dfn[v]（這裡不再詳細說），是以棧裡v以其v以上的頂點組成的子圖是一個極大強連通分量。
【時間複雜度】
因為所有的點都剛好進過一次棧，所有的邊都通路的過一次，是以時間複雜度為O（n+m）
代碼如下：
1 // 強連通分量縮點 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <stack> 6 7 using namespace std; 8 9 const int MAX = 105; 10 int map[MAX][MAX]; 11 int low[MAX], DFN[MAX], IN[MAX], OUT[MAX], instack[MAX], t[MAX]; 12 int n, order, res, ans; 13 stack<int> S; 14 15 void init() 16 { 17 memset(map, 0, sizeof(map)); 18 memset(low, 0, sizeof(low)); 19 memset(DFN, 0, sizeof(DFN)); 20 memset(IN, 0, sizeof(IN)); 21 memset(OUT, 0, sizeof(OUT)); 22 memset(instack, 0, sizeof(instack)); 23 memset(t, 0, sizeof(t)); 24 while(!S.empty()) 25 S.pop(); 26 res = 0; 27 order = 0; 28 } 29 30 int min(int x, int y) 31 { 32 return x < y ? x : y; 33 } 34 35 void tr(int u) 36 { 37 int v; 38 DFN[u] = low[u] = ++order; 39 instack[u] = 1; 40 S.push(u); 41 for (int i = 1; i <= n; i++) 42 { 43 if(map[u][i]) 44 { 45 if(!DFN[i]) 46 { 47 tr(i); 48 low[u] = min(low[u], low[i]); 49 } 50 else if(instack[i]) 51 low[u] = min(low[u], DFN[i]); 52 } 53 } 54 if(DFN[u] == low[u]) 55 { 56 ++res; // res 代表強連通分量的個數 57 do 58 { 59 v=S.top(); 60 S.pop(); 61 instack[v] = 0; 62 t[v] = res; 63 }while(v != u); 64 } 65 } 66 67 void tarjan() 68 { 69 for (int i = 1; i <= n; i++) 70 if(!DFN[i]) 71 tr(i); 72 } 73 74 void solve() 75 { 76 for (int i = 1;i <= n; i++) 77 { 78 for (int j = 1;j <= n; j++) 79 if(map[i][j]) // 統計每個強連通分量縮點的入度和出度 80 { 81 ++IN[t[i]]; 82 ++OUT[t[j]]; 83 } 84 } 85 int xx, yy; 86 xx = yy = 0; 87 for(int i = 1; i <= res; i++) 88 { 89 if(IN[i]==0) 90 xx++; 91 else if(OUT[i]==0) 92 yy++; 93 } 94 ans = xx > yy ? xx : yy; // 結果為縮點後的有向圖中出度為0或者入度為0中的大者 95 } 96 97 int main() 98 { 99 int T, x; 100 scanf("%d", &T); 101 while (T--) 102 { 103 init(); 104 scanf("%d",&n); 105 for (int i = 1; i <= n; i++) 106 { 107 while (scanf("%d", &x), x) 108 map[i][x] = 1; 109 } 110 tarjan(); 111 solve(); 112 if(res == 1) 113 printf("0\n"); 114 else 115 printf("%d\n", ans); 116 } 117 return 0; 118 }注：部分用到強連通分量的題目總結：
POJ 2186 Popular Cows (基礎)
POJ 2553 The Bottom of a Graph（alpc OJ 1274）(基礎)
POJ 1236 Network of Schools (基礎)
2010中南賽 light sources（alpc OJ） (基礎)
POJ 2762 Going from u to v or from v to u? (中等，弱連通分量 )
POJ 3160 Father Christmas flymouse(難，DP題)
POJ 1904 King‘s Quest(難，推薦，非縮點，比對思想與強連通分量的轉化)
-