題目描述

有n個同學(xué)（編號為1到n）正在玩一個信息傳遞的游戲。在游戲里每人都有一個固定的信息傳遞對象，其中，編號為i的同學(xué)的信息傳遞對象是編號為Ti同學(xué)。

游戲開始時，每人都只知道自己的生日。之后每一輪中，所有人會同時將自己當(dāng)前所知的生日信息告訴各自的信息傳遞對象（注意：可能有人可以從若干人那里獲取信息，但是每人只會把信息告訴一個人，即自己的信息傳遞對象）。當(dāng)有人從別人口中得知自己的生日時，游戲結(jié)束。請問該游戲一共可以進行幾輪？

輸入輸出格式

輸入格式：

輸入共2行。

第1行包含1個正整數(shù)n表示n個人。

第2行包含n個用空格隔開的正整數(shù)T1,T2,……,Tn其中第i個整數(shù)Ti示編號為i

的同學(xué)的信息傳遞對象是編號為Ti的同學(xué)，Ti≤n且Ti≠i

數(shù)據(jù)保證游戲一定會結(jié)束。

輸出格式：

輸出共 1 行，包含 1 個整數(shù)，表示游戲一共可以進行多少輪。

輸入輸出樣例

輸入樣例#1：
5 2 4 2 3 1 輸出樣例#1：
3

說明

樣例1解釋

游戲的流程如圖所示。當(dāng)進行完第 3 輪游戲后， 4 號玩家會聽到 2 號玩家告訴他自

己的生日，所以答案為 3。當(dāng)然，第 3 輪游戲后， 2 號玩家、 3 號玩家都能從自己的消息

來源得知自己的生日，同樣符合游戲結(jié)束的條件。

對于 30%的數(shù)據(jù)， n ≤ 200；

對于 60%的數(shù)據(jù)， n ≤ 2500；

對于 100%的數(shù)據(jù)， n ≤ 200000。

算法：深搜

分析：第一次寫炸了，回過頭來想一想，發(fā)現(xiàn)算法是錯誤的，這道題正解應(yīng)該是圖論，拓?fù)渑判蛘易钚…h(huán)， 但深搜也還是很好理解的。（這種思路是借鑒某位大牛的程序才恍然大悟的) 用三個數(shù)組，a記邊（讀入),b記在以哪個枝點為開始的環(huán)內(nèi)，f記此點在環(huán)內(nèi)的步數(shù)。 隨便取一個點i為環(huán)的開端，沿著邊走下去，記下步數(shù)存入f中，再將b[k]賦成i。 當(dāng)遇到一個點b[k]不為0時，有兩種情況： 1.成為新環(huán)，跳出并取小。 2.遇到舊環(huán)，特判b[k]<>i那么不計。 還有一個問題，怎樣算出環(huán)的長度？f數(shù)組會多出，因為b數(shù)組記的不是環(huán)，會有另外的點。 設(shè)num是b數(shù)組內(nèi)的點數(shù)，j是成為新環(huán)時判斷的點，那么，環(huán)長就是num-f[j] (可以畫個圖理解一下,畢竟是tg的題，不那么容易想到） vari,j,k,n,m,ans,num:longint;a,b,f:array[0..200000+7] of longint; beginread(n);for i:=1 to n do read(a[i]);fillchar(b,sizeof(b),0);fillchar(f,sizeof(f),0);ans:=maxlongint;for i:=1 to n dobeginif b[i]<>0 then continue;k:=i;num:=0;while b[k]=0 dobeginf[k]:=num;inc(num);b[k]:=i;k:=a[k];end;if b[k]<>i then continue;num:=num-f[k];if num<ans then ans:=num;end;writeln(ans); end.

?

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

總結(jié)

以上是生活随笔為你收集整理的tg2015 信息传递 （洛谷p2661)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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