Description

某校科技節到了，有? 個同學（編號為1到?）正在玩一個信息傳遞的游戲。在游戲里每人都有一個固定的信息傳遞對象，其中，編號為? 的同學的信息傳遞對象是編號為??的同學。
　　游戲開始時，每人都只知道自己的生日。之后每一輪中，所有人會同時將自己當前所知的生日信息告訴各自的信息傳遞對象（注意：可能有人可以從若干人那里獲取信息，但是每人只會把信息告訴一個人，即自己的信息傳遞對象）。當有人從別人口中得知自己的生日時，游戲結束。請問該游戲一共可以進行幾輪？

Input

輸入文件名為game.in。輸入共2行。第1行包含1個正整數?，表示? 個人；第2行包含? 個用空格隔開的正整數?1,?2,……,??，其中第? 個整數??表示編號為? 的同學的信息傳遞對象是編號為Ti 的同學，??≤? 且??≠?。數據保證游戲一定會結束。

Output

輸出文件名為game.out。輸出共1行，包含1個整數，表示游戲一共可以進行多少輪。

Sample Input

5
2 4 2 3 1
Sample Output

3
輸入輸出樣例1說明：

游戲的流程如圖所示。當進行完第3輪游戲后，4號玩家會聽到2號玩家告訴他自己的生日，所以答案為3。當然，第3輪游戲后，2號玩家、3號玩家都能從自己的消息來源得知自己的生日，同樣符合游戲結束的條件。
Hint

對于30%的數據，?≤200；；對于60%的數據，?≤2500；對于100%的數據，?≤200000。

.
.
.
.
.
分析
考場一看，就打了70分的暴力
暴力：
實際上，信息的傳遞可以寫成一條環：1-2-4-3-2
這就可用dfs來做(dfs搜鏈時更快)
每次從一個人出發搜，記錄每個人的時間
但這dfs會超時，我們需要加點優化

暴力的正解：
對于一次查找環中，由于此次查找中至多只有一個環，而此環已經確定，所以再有外部的鏈介入此環，它的狀態仍然不變。所以可以加個判斷，如果走到了已經被查找過的節點，便直接跳出。

.
.
.
.
70分：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int f[100001],tj,a[10000],b[10000],ans=2147483647; bool f1[200001];void dfs(int x,int sum) {tj++;a[tj]=x;b[x]++;if (b[x]!=2) dfs(f[x],sum+1); else{ans=min(sum,ans);return;} }int main() {freopen("game.in","r",stdin);freopen("game.out","w",stdout);int n;scanf("%d",&n);for (int i=1;i<=n;i++){int x;scanf("%d",&x);f[i]=x;}for (int i=1;i<=n;i++){memset(a,0,sizeof(a));memset(b,0,sizeof(b));tj=0;dfs(i,0);}cout<<ans;fclose(stdin);fclose(stdout);return 0; }

.
.
.
.
100分：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;int ans=2147483647,n,a[300003],f[300003]; bool bz[300003],f1[300003];inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w; }void dfs(int x,int num) {if (bz[x]==true) return;if (f1[x]==true) ans=min(ans,num-a[x]); else{f1[x]=true;a[x]=num;dfs(f[x],num+1);bz[x]=true;} }int main() {scanf("%d",&n);for (int i=1;i<=n;i++)f[i]=read();for (int i=1;i<=n;i++)dfs(i,0);printf("%d",ans);return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/11094908.html

總結

以上是生活随笔為你收集整理的2019年东莞特长生 游戏(洛谷 P2661 信息传递)的全部內容，希望文章能夠幫你解決所遇到的問題。

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