【題目描述】

在FJOI2010夏令營快要結(jié)束的時(shí)候，很多營員提出來要把整個(gè)夏令營期間的資料刻錄成一張光盤給大家，以便大家回去后繼續(xù)學(xué)習(xí)。組委會覺得這個(gè)主意不錯！可是組委會一時(shí)沒有足夠的空光盤，沒法保證每個(gè)人都能拿到刻錄上資料的光盤，怎么辦呢？！

DYJ分析了一下所有營員的地域關(guān)系，發(fā)現(xiàn)有些營員是一個(gè)城市的，其實(shí)他們只需要一張就可以了，因?yàn)橐粋€(gè)人拿到光盤后，其他人可以帶著U盤之類的東西去拷貝啊！

他們愿意某一些人到他那兒拷貝資料，當(dāng)然也可能不愿意讓另外一些人到他那兒拷貝資料，這與我們FJOI宣揚(yáng)的團(tuán)隊(duì)合作精神格格不入！！！

現(xiàn)在假設(shè)總共有N個(gè)營員（2≤N≤200），每個(gè)營員的編號為1~N。DYJ給每個(gè)人發(fā)了一張調(diào)查表，讓每個(gè)營員填上自己愿意讓哪些人到他那兒拷貝資料。當(dāng)然，如果A愿意把資料拷貝給B，而B又愿意把資料拷貝給C，則一旦A獲得了資料，則B，C都會獲得資料。

現(xiàn)在，請你編寫一個(gè)程序，根據(jù)回收上來的調(diào)查表，幫助DYJ計(jì)算出組委會至少要刻錄多少張光盤，才能保證所有營員回去后都能得到夏令營資料？

【輸入】

先是一個(gè)數(shù)N，接下來的N行，分別表示各個(gè)營員愿意把自己獲得的資料拷貝給其他哪些營員。即輸入數(shù)據(jù)的第i+1行表示第i個(gè)營員愿意把資料拷貝給那些營員的編號，以一個(gè)0結(jié)束。如果一個(gè)營員不愿意拷貝資料給任何人，則相應(yīng)的行只有1個(gè)0，一行中的若干數(shù)之間用一個(gè)空格隔開。

【輸出】

一個(gè)正整數(shù)，表示最少要刻錄的光盤數(shù)。

【輸入樣例】

5
2 4 3 0
4 5 0
0
0
1 0

?

【輸出樣例】

1

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<set> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 501 #define MOD 123 #define E 1e-6 using namespace std; int g[N][N],pre[N]; int main() {int n,j;cin>>n;for(int i=1;i<=n;i++)while(scanf("%d",&j)!=EOF && j)g[i][j]=1;for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)for(int j=1;j<=n;j++)if(g[i][k]&&g[k][j])g[i][j]=1;for(int i=1;i<=n;i++)pre[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j])pre[j]=pre[i];int cnt=0;for(int i=1;i<=n;i++)if(pre[i]==i)cnt++;cout<<cnt<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的刻录光盘（信息学奥赛一本通-T1383）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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