題目描述

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

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

輸入格式

共22行。

第11行包含1個正整數(shù)?nn?，表示?nn?個人。

第22行包含?nn?個用空格隔開的正整數(shù)?T_1,T_2,\cdots\cdots,T_nT1?,T2?,??,Tn??，其中第?ii?個整數(shù)?T_iTi??表示編號為?ii?的同學(xué)的信息傳遞對象是編號為?T_iTi??的同學(xué)，?T_i \leq nTi?≤n?且?T_i \neq iTi?≠i?。

輸出格式

11個整數(shù)，表示游戲一共可以進(jìn)行多少輪。

輸入輸出樣例

輸入 #1復(fù)制 5 2 4 2 3 1 輸出 #1復(fù)制 3

說明/提示

樣例1解釋

游戲的流程如圖所示。當(dāng)進(jìn)行完第33?輪游戲后，?44號玩家會聽到?22?號玩家告訴他自己的生日，所以答案為?33。當(dāng)然，第?33?輪游戲后，22號玩家、?33?號玩家都能從自己的消息來源得知自己的生日，同樣符合游戲結(jié)束的條件。

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

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

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

題解:找個環(huán)qwq具體我是看洛谷題解的%%%所以把題解搬運來咯！！
? ? ? ? ?

我們在連接一個點到另一個點之前，先用并查集判斷是否構(gòu)成一個環(huán)，如果是的話，我們就可以記錄下這個答案，然后維護(hù)最小的答案。

那么，如果構(gòu)成一個環(huán)的話，怎么記錄它的長度呢？

我們可以先定義一個變量cnt，在并查集獲取祖先的函數(shù)中使cnt的值加1，最后函數(shù)結(jié)束時就能得到這個環(huán)的長度了qwq！

同時，如果構(gòu)成了一個環(huán)，就不需要把這個環(huán)的結(jié)尾接上，否則會陷入死循環(huán)！！

最后附上短短的代碼：

// luogu-judger-enable-o2 #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int N=200002; const int oo=0x3f3f3f3f; int n,fa[N],ans=oo; int find(int x,int &yc) {yc++;if(fa[x]!=x) return find(fa[x],yc);else return x; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++)fa[i]=i;int yc,biu;for(int i=1;i<=n;i++) {yc=0; scanf("%d",&biu);if(find(biu,yc)==i)ans=min(ans,yc);else fa[i]=biu;}printf("%d\n",ans);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/wuhu-JJJ/p/11318579.html

總結(jié)

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

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