P2661 [NOIP2015 提高组] 信息传递

题目简述

第i个人可以将自己的信息传给第\(t_i\)个人，当有人从别人那里得到自己信息时就结束，问最少要进行多少轮

思路

这题感觉真的很巧妙，将每个人看作一个点，对应关系看作是条边的话，那么则是找图里最小的环
本题特殊的地方在于，从任一结点出发，最后一定是能走到一个环里面的qwq
因为总人数是有限的，假设每次都会走到一个新的人那里，那么到最后一定会走到重复的人那
所以我们可以每次将每个人所在的环顺着走完，其实每个人要么在环内，要么在一条链加一个环内，最后将走过的环都标记上，所以每个节点也只会访问一遍，时间复杂度 \(\theta(n)\)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t[N],cir[N],ste[N];
int main(){
  int n,kdl=0;
  int ans=0x3f3f3f3f;
  cin>>n;
  for(int i=1;i<=n;i++)cin>>t[i];
  for(int i=1;i<=n;i++){
    if(cir[i])continue;
    kdl++;
    int tmp=i,cnt=0;
    //cir[tmp]=kdl;
    while(cir[tmp]==0){
      cir[tmp]=kdl;
      ste[tmp]=++cnt;
      tmp=t[tmp];  
    }
    if(cir[tmp]!=kdl)continue;
    else ans=min(ans,cnt-ste[tmp]+1);
  }
  cout<<ans<<endl;
  return 0;
}