L2-026 小字辈 (25 分)

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

9
2 6 5 5 -1 5 6 4 7

输出样例：

4
1 9

AC代码：
使用bfs算法解决问题不会超时

#include<bits/stdc++.h>
#include<queue> 
using namespace std;
const int MAXN = 1e5+5;

vector<int> G[MAXN];

struct P{
  int id;
  int layer;
};

int main(){
  
  int n;
  cin >> n;
  
  for(int i = 1; i <= n; i++){
    int t;
    cin >> t;
    if(t==-1)t=0;
    G[t].push_back(i);
   }

  queue<P> q;
  q.push({0,0});
  
  int maxm = -0x4f4f4f;
  vector<int> re;
  while(!q.empty()){
    P p = q.front();
    q.pop();
    int id = p.id;
    int layer = p.layer;
    if(layer > maxm){
      maxm=layer;
      re.clear();
    }
    if(G[id].size()){
      for(int i=0; i < G[id].size(); i++){
        q.push({G[id][i],layer+1});
      }
    }else{
      re.push_back(id);
    }
  }
  
  cout << maxm << endl;
  sort(re.begin(),re.begin());
  
  for(int i = 0; i < re.size(); i++){
    if(i)cout <<" ";
    cout << re[i];
  }
  
  return 0;
}

暴力解决会超时

#include<bits/stdc++.h>
 
using namespace std;
const int MAXN = 1e5+5;

int farther[MAXN];
int layer[MAXN];


int find(int x){
  if(layer[x]!=-1){
    return layer[x];
    
  }else{
    int cnt = 0;
  int a = x;
  
  while(x!=-1){
    x = farther[x];
    cnt++;
  }
  layer[a]=cnt;
  
  return cnt;
  }
  
}
int main(){
  int n;
  cin >> n;
  fill(layer,layer+MAXN,-1);
  
  for(int i =1 ; i <= n; i++){
    cin >> farther[i];
  }
  int maxm = -0x4f4f;
  
  for(int i = 1; i <= n; i++){
    int lay= find(i);
    layer[i] = lay;
    if(lay > maxm)maxm = lay;
  }
 
  vector<int> re;
  
  for(int i = 1; i <= n; i++){
    if(layer[i]==maxm)re.push_back(i);  
  }
  cout << maxm << endl;
  
  
  for(int i = 0; i <re.size(); i++){
    if(i)cout<<" ";
    cout << re[i];
  }
    
    
  return 0;
}