校園網絡

時間限制：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

分析：把每個系抽象成一個節點，對每個節點求出度和入度，若某節點入度為0，當此節點自身無軟件可用時，也無法從其他節點獲取軟件；若節點出度為0，當只有此節點有軟件時，其他節點都無軟件可用。所以要使每個節點節點都有軟件用，即求入度為0節點的個數+出度為0節點的個數。

#include <iostream> #include <cstring> using namespace std;int book1[101]; int book2[101]; int main() {int num;int n;int temp;cin>>num;int res;while(num--){res = 0;cin>>n;memset(book1,0,sizeof(book1)); memset(book2,0,sizeof(book2));for(int i=1;i<=n;i++){while(cin>>temp&&temp!=0){book1[temp]++;book2[i]++;}}for(int i=1;i<=n;i++){if(book1[i]==0)res++;if(book2[i]==0)res++; }cout<<res<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的强连通Tarjan NYOJ 120 校园网络的全部內容，希望文章能夠幫你解決所遇到的問題。

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