洛谷 P2661 信息传递

题目描述

有 n个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 iii 的同学的信息传递对象是编号为 Ti的同学。

游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入格式

共2行。第1行包含1个正整数 n ，表示 n 个人。第2行包含 n 个用空格隔开的正整数 T1,T2,⋯⋯ ,Tn​ ，其中第 iii 个整数 Ti 表示编号为 i的同学的信息传递对象是编号为 Ti​ 的同学， Ti≤n 且 Ti≠i。

输出格式

1个整数，表示游戏一共可以进行多少轮。

输入输出样例

输入 #1 复制

5
2 4 2 3 1

输出 #1 复制

3

采用广度优先遍历解题，是一个广度优先遍历图的例子。

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int num_edge=0,n,a,head[200001],que[200001],hed,tail,mint=200001,mark[200001],step[200001],markt[200001];
struct Edge
{
 int to,next;
}edge[200001];

void add_edge(int from,int to)
{
 edge[++num_edge].next=head[from];
 edge[num_edge].to=to;
 head[from]=num_edge;
}

int min(int aa,int bb)
{
 return aa>bb?bb:aa;
}
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>a;
  add_edge(i,a);
 }
 for(int i=1;i<=n;i++)
 {
  if(mark[i]==1) continue;
  hed=0;tail=1;
  que[tail]=i;step[i]=0;
  //printf("%d",i);
  while(hed<tail)
  { hed++;
   int headt=que[hed];
   //printf(">>%d(%d)",headt,step[headt]);
   if(step[headt]>mint) break;
   if(headt==i&&hed!=1){
    mint=min(mint,step[i]);
    //printf(" %d   %d",step[i],mint);
    break;
   }
  for(int j=head[headt];j!=0;j=edge[j].next)
   if(mark[edge[j].to]==0)
   { mark[edge[j].to]=1;markt[edge[j].to]=i;
    que[++tail]=edge[j].to;step[edge[j].to]=step[headt]+1;
   }
   else if(mark[edge[j].to]==1&&markt[edge[j].to]==i)
   {
    mint=min(mint,step[headt]+1-step[edge[j].to]);
    //printf(" %d   %d",step[headt]+1-step[edge[j].to],mint);
    //markt[i]=1;
   }
  }
 // memset(mark,0,sizeof(int)*200001);
 // printf(" ");
 }
 printf("%d",mint);
 return 0;
 }

 

　　　　　　建图，广度优先遍历。

需要注意的地方是粗暴的广度优先遍历会超时，我们由分析可得，图只有三种情况，链或环或一个环连一条链。

每遍历到一个点就标记起来不用释放，因为上述三种情况都是遍历过的点就没有必要再作为起点遍历一遍，这种时候我们只需要判断是否成环，如果成环就可以记录环上的点的个数。

另外需要注意的是判断下一个点已经被标记了不代表成环，因为我们没有重置mark数组。因此我们需要开一个markt数组记录一个点被标记时的出发点。如果遍历到下一个点被标记再判断

markt的值是否是此时的出发点，如果是则成环，如果不是就不成环直接跳出此次遍历。