信息傳遞

題目描述

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

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

輸入輸出格式

　　輸入格式：

　　輸入共2行。

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

　　第2行包含n個(gè)用空格隔開的正整數(shù)T1,T2,……,Tn其中第i個(gè)整數(shù)Ti示編號(hào)為i的同學(xué)的信息傳遞對(duì)象是編號(hào)為Ti的同學(xué)，Ti≤n且Ti≠i

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

?

　　輸出格式：

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

輸入輸出樣例

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

說明

　　樣例1解釋

?

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

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

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

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

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

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

?

俺的題解

　　很明顯，這道題可以轉(zhuǎn)換為圖論中求最小環(huán)的問題。

　　

　　（本來還找了一下畫圖論的圖的軟件，后來發(fā)現(xiàn)PPT的功能已經(jīng)足夠強(qiáng)大= =）

　　把每個(gè)同學(xué)當(dāng)做節(jié)點(diǎn)，i和Ti之間連有向邊。

　　去年刷到這道題時(shí)一直覺得環(huán)的特征不明顯，今年對(duì)圖論理解深刻了點(diǎn)，就好些了……

　　求環(huán)就有很多種方式咯，在這里說兩種。

方法一：拓?fù)渑判?/h2>

　　　　拓?fù)渑判驎r(shí)會(huì)不斷刪掉入度為0的點(diǎn)，然而環(huán)中的點(diǎn)入度永遠(yuǎn)不會(huì)為0，于是環(huán)被保留了下來。

　　　　憑借這個(gè)性質(zhì)搜索剩下的環(huán)中最小的長度。　

　 ?方法二：求強(qiáng)連通分量

　　　　因?yàn)槊客瑢W(xué)都只有一位固定對(duì)象，所以每個(gè)節(jié)點(diǎn)出度都為1。此時(shí)求強(qiáng)連通分量等同于求環(huán)。

?

俺的代碼

　　方法一：

1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 int n; 7 int ans=10000000; 8 struct node 9 { 10 int next; 11 int cnt; 12 bool bj; 13 node(){next=0;cnt=0;bj=0;} 14 }a[200001]; 15 queue <node> que; 16 int main() 17 { 18 cin>>n; 19 for(int i=1;i<=n;i++) 20 { 21 cin>>a[i].next; 22 a[a[i].next].cnt++;//記錄入度 23 } 24 //拓?fù)?/span> 25 for(int i=1;i<=n;i++) 26 { 27 if(a[i].cnt == 0) 28 { 29 que.push(a[i]); 30 a[i].bj=1; 31 } 32 } 33 while(!que.empty()) 34 { 35 node i=que.front(); 36 que.pop(); 37 if(--a[i.next].cnt==0) 38 { 39 que.push(a[i.next]); 40 a[i.next].bj=1; 41 } 42 } 43 44 for(int i=1;i<=n;i++) 45 { 46 if(a[i].bj==0) 47 { 48 int j=i,count=0; 49 do 50 { 51 count++; 52 a[j].bj=1; 53 j=a[j].next; 54 }while(j!=i); 55 ans=min(ans,count); 56 } 57 } 58 cout<<ans; 59 return 0; 60 } 點(diǎn)擊就送屠龍寶刀

　　方法二：

1 /* 2 */ 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 #include<vector> 7 using namespace std; 8 9 int n,scc=0,idx=0,s[200700],low[200700],dfn[200700],top=0; 10 bool in_stack[200700]; 11 int ans=10000000; 12 vector<int> edge[200700]; 13 int length[200700]; 14 15 void tarjan(int u) { 16 dfn[u] = low[u] = ++idx;//init 17 s[top++] = u;//壓棧 18 in_stack[u] = true; 19 for (int i = 0; i < edge[u].size();i++) { 20 int v = edge[u][i]; 21 if (!dfn[v]) {//未被訪問過 22 tarjan(v);//continue 23 low[u] = min(low[u], low[v]); 24 } 25 else if (in_stack[v]) {//如果還在棧內(nèi) 26 low[u] = min(low[u], dfn[v]); 27 } 28 } 29 int size=0; 30 if (dfn[u] == low[u]) {//如果u是強(qiáng)聯(lián)通的根 31 do { 32 size++; 33 in_stack[s[--top]] = false;//退棧 34 } while (s[top] != u);//走完一個(gè)環(huán)返回 35 if(size != 1) 36 ans=min(ans,size); 37 } 38 } 39 int main(){ 40 scanf("%d",&n); 41 for(int i=1;i<=n;i++){ 42 int v; 43 scanf("%d",&v); 44 edge[i].push_back(v); 45 } 46 for(int i=1;i<=n;i++) 47 tarjan(i); 48 printf("%d",ans); 49 return 0; 50 } 點(diǎn)擊就送屠龍寶刀

?

俺的反思

　　　　傻X錯(cuò)誤：這張圖可能不連通！比如：

?　　

　　所以需要循環(huán)tarjan...o(╯□╰)o

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

總結(jié)

以上是生活随笔為你收集整理的[拓扑排序/强联通分量] [NOIP201402] 信息传递的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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