題目大意：
一些學校連成了網絡， 在學校之間存在某個協議:每個學校都維護一張傳送表，表明他們要負責將收到的軟件傳送到表中的所有學校。如果A在B的表中，那麼B不一定在A的表中。
現在的任務就是，給出所有學校及他們維護的表，問1、如果所有學校都要被傳送到，那麼需要幾份軟件備份；2、如果只用一份軟件備份，那麼需要添加幾條邊？
題目解法：
這道題就是求學校之間連成網絡的強聯通分量。第一問中軟件只要在一個分量中存在一份，那麼分量中的其他學校必然也可以拿到這份軟件；第二問中要所有學校都連成一個強聯通分量，只需要將圖中的強聯通分量互相之間聯通就好了。添加的邊數就是縮點後入度為0的點和出度為0的點的最大值（可意會不可言傳。。）。
題目源碼：關鍵部分都用注釋標明了
[html]
//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define MAXN 110
#define INF 0x3f3f3f3f
int n;
int map[MAXN][MAXN];
int low[MAXN];
int dfn[MAXN];
int stack[MAXN], head;
int instack[MAXN];
int belong[MAXN];
int in[MAXN];
int out[MAXN];
int index, cnt;
int min(int a, int b)
{
return a < b ? a : b;
}
int max(int a, int b)
{
return a > b ? a : b;
}
void init()
{
int i, j;
int temp;
memset(map, 0, sizeof(map));
memset(dfn, -1, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(instack, 0, sizeof(instack));
index = cnt = 1;
head = 0;
for(i= 1; i <= n; i++)
{
while(scanf("%d", &temp) && temp)
{
map[i][temp] = 1;
}
}
}
void tarjan(int x)
{
int i, a;
low[x] = dfn[x] = index; // 剛搜到一個節點時low = dfn
index++;
stack[++head] = x; // 將該節點入棧
instack[x] = 1; // 將入棧標記設置為1
for(i = 1; i <= n; i++) // 遍歷入棧節點的邊
{
if(!map[x][i]) // 如果兩點之間沒有邊
continue; // 不用管它
if(dfn[i] == -1) // 如果新搜索到的節點是從未被搜索過
{
tarjan(i); // 那自然就得搜索這個節點
low[x] = min(low[x], low[i]); // 回溯的時候改變當前節點的low值
}
else if(instack[i]) // 如果新搜索到的節點已經被搜索過而且現在在棧中
{
low[x] = min(low[x], dfn[i]); // 更新當前節點的low值，這裡的意思是兩個節點之間有一條可達邊，而前面
} // 而前面節點已經在棧中，那麼後面的節點就可能和前面的節點在一個聯通分量中
}
if(low[x] == dfn[x]) // 最終退回來的時候 low == dfn ， 沒有節點能將根節點更新，那
{ // low == dfn 的節點必然就是根節點
int temp;
while(1) // 一直出棧到此節點， 這些元素是一個強聯通分量
{
temp = stack[head--]; // 彈出棧元素
belong[temp] = cnt; // 為了方便計算，將強聯通分量進行標記
instack[temp] = 0; // 將棧內標記置為0
if(temp == x) // 一直彈到x出現為止
break;
}
cnt++;
}
}
void solve()
{
int i, j;
int t1, t2;
while(scanf("%d", &n) != EOF) //
{
init(); // 初始化
for(i = 1; i <= n; i++) //
if(dfn[i] == -1) // 如果某點沒被訪問過，則對其進行tarjan
tarjan(i); // tarjan的成果是得到了一個belong數組，記錄每個節點分別屬於哪個強聯通分量
for(i = 1; i <= n; i++) // 遍歷每條邊，找到縮點之後的邊
{
for(j = 1;j <= n; j++)
{
if(map[i][j] && belong[i] != belong[j]) // 兩點之間有邊，但不是屬於一個強聯通分量的邊
{
out[belong[i]]++; // 縮點後的點入度+1
in[belong[j]]++;// 縮點後的點出度+1
}
}
}
t1 = 0, t2 = 0;
for(i = 1; i < cnt; i++)
{
if(in[i] == 0)
t1++;
if(out[i] == 0)
t2++;
}
if(cnt == 2)
printf("1\n0\n");
else
printf("%d\n%d\n", t1, max(t1, t2));
}
}
int main()
{
#ifdef LOCAL
freopen("poj1236.txt", "r", stdin);
// freopen(".txt", "w", stdout);
#endif
solve();
return 0;
}
參考資料：有向圖強聯通分量的tarjan算法
不明白之處細細鑽研意會更有收獲。。
作者：huzhengnan
