// 拓扑排序 O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=200010;
int n,t[N],rd[N],ans=1e9;
bool vis[N];

void topo(){
  queue<int> q;
  for(int i=1;i<=n;i++) if(!rd[i]) q.push(i);
  while(!q.empty()){
    int u=q.front();q.pop();
    vis[u]=1; //u点能出队，说明其入度为0，标记u点不在环内
    if(--rd[t[u]]==0) q.push(t[u]);
  }
}
void dfs(int x,int s){ //深搜求环长
  if(vis[x]){ //发现x点已访问，那么更新答案
    ans=min(ans,s); 
    return;
  }
  vis[x]=1; //标记x点已访问
  dfs(t[x],s+1);
}
signed main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>t[i];  //下标i向值ti连边
    rd[t[i]]++; //ti入度+1
  }
  topo();
  for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0); //如果i在环内，则深搜
  cout<<ans;
}

// 有向最小环 并查集 
#include<bits/stdc++.h>
using namespace std;

int n,cnt,ans=2e9;
int fa[200005];

int find(int x){
  ++cnt;
  return fa[x]==x?x:find(fa[x]);
}
int main(){
  cin>>n;
  for(int i=1; i<=n; i++) fa[i]=i;
  for(int i=1,t; i<=n; i++){
    cin>>t;
    cnt=0;
    find(t)==i?ans=min(ans,cnt):fa[i]=t;
  }
  cout<<ans;
}

// 有向最小环 tarjan O(n)
#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int n;
int dfn[N],low[N],tim,stk[N],top,siz[N],scc[N],cnt;
vector<int> e[N];

void tarjan(int x){
  dfn[x]=low[x]=++tim; stk[++top]=x;
  for(int y:e[x]){
    if(!dfn[y]){
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) low[x]=min(low[x],dfn[y]);
  }
  if(low[x]==dfn[x]){
    ++cnt;
    while(1){
      int y=stk[top--];
      scc[y]=cnt;
      siz[cnt]++;
      if(y==x) break;
    }
  }
}
signed main(){
  cin>>n;
  for(int i=1,x;i<=n;i++){
    cin>>x;
    e[i].push_back(x);
  }
  for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
  
  int ans=2e9;
  for(int i=1;i<=n;i++) 
    if(siz[i]>=2) ans=min(ans,siz[i]);
  cout<<ans;
}

题目分析

该问题涉及信息传播的轮次计算，玩家通过传递生日信息确定自己的生日，求第一个玩家得知自己生日所需的最少轮数。数据范围n≤200000，需设计高效算法（O(n)或O(n log n)）。

核心思路

问题可转化为有向图中信息传播的最短路径问题。玩家间的传递关系构成有向图，信息从“信息源”节点开始传播，每轮传播到直接邻居，求信息首次到达某个节点的轮数。答案即为该节点到信息源的最短路径长度。

算法设计

1. 图模型构建：将玩家及传递关系抽象为有向图，节点为玩家，有向边u→v表示玩家u可向v传递信息。
2. BFS求最短路径：以可能的“信息源”节点为起点，通过BFS计算各节点的信息传播时间，取首次到达任意节点的最大时间（即最长路径）。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);  // 有向图邻接表
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // u可向v传递信息
    }
    
    // BFS求从起点到各节点的最短路径
    auto bfs = [&](int start) -> int {
        vector<int> dist(n + 1, -1);
        queue<int> q;
        dist[start] = 0;
        q.push(start);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return *max_element(dist.begin() + 1, dist.end());  // 最大传播时间
    };
    
    // 假设信息源为1，求最大传播时间
    cout << bfs(1) << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，BFS遍历所有节点和边，n为玩家数量。
• 空间复杂度：O(n)，邻接表和距离数组的空间开销。

说明

代码通过BFS计算信息从起点传播到所有节点的最大时间，即首次有玩家得知生日的轮数。若存在多个信息源，需在所有可能起点中取最小值。样例中4号玩家在第3轮得知生日，对应图中最长路径为3。