当前位置:网站首页>PTA 7-4 small generation (DFS)
PTA 7-4 small generation (DFS)
2022-07-27 00:09:00 【Muxi Krystal】
https://pintia.cn/problem-sets/1259041418971803648/problems/1259047109883162624
( Title link above )
The question :
Given the genealogy of a large family , Please give a list of the youngest generation .
Answer key :
Node design :
struct tnode{
int parent;
int num;
int level;// Record seniority , Which layer of the tree
}node[100005];
Ideas : For each node , Search deeply until its ancestor root node returns , When tracing back, the number of layers of each layer is equal to the number of layers of the previous layer plus one . If you find a node level Not for 0, And go straight back to , When backtracking, add from the level of this node .
AC Code :
#include <iostream>
using namespace std;
int n,lev;
struct tnode{
int parent;
int num;
int level;
}node[100005];
void dfs(int now){
if(node[now].parent==-1){
node[now].level=1;
return;
}
if(node[now].level!=0){
return;
}
int next=node[now].parent;
dfs(next);
node[now].level=node[next].level+1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>node[i].parent;
node[i].num=i;
}
int maxlev=-1;
for(int i=1;i<=n;i++){
dfs(i);
lev=node[i].level;
maxlev=max(maxlev,lev);
}
int flag=0;
cout<<maxlev<<endl;
for(int i=1;i<=n;i++){
if(node[i].level==maxlev){
if(!flag){
cout<<i; flag=1;
}
else cout<<" "<<i;
}
}
cout<<endl;
return 0;
}
边栏推荐
- Relationship between Unicode and UTF-8
- Last week's hot review (7.11-7.17)
- Pytorch data pipeline standardized code template
- C语言数组
- Part II - C language improvement_ 13. Recursive function
- 百度网址收录
- Chapter 1 requirements analysis and SSM environment preparation
- 4-4 对象生命周期
- 第二部分—C语言提高篇_6. 多维数组
- Chapter 2 develop user traffic interceptors
猜你喜欢

MVC three-tier architecture

The difference between SQL join and related subinquiry

第3章 跨域问题

18、打开、保存文件对话框使用小记

Transformers is a graph neural network

The basic operation of data tables in MySQL is very difficult. This experiment will take you through it from the beginning

第二部分—C语言提高篇_13. 递归函数

Azure Synapse Analytics 性能优化指南(4)——使用结果集缓存优化性能

Meeting OA my meeting

Part II - C language improvement_ 13. Recursive function
随机推荐
证券公司哪家佣金最低?网上开户安全吗
Azure Synapse Analytics 性能优化指南(4)——使用结果集缓存优化性能
Typesript generic constraint
Method of realizing program startup and self startup through registry
Design of alcohol detector based on 51 single chip microcomputer
Arthas quick start
Galaxy securities online account opening commission, is online account opening safe for customer managers
Method of setting QQ to blank ID
Tensorflow2.0 deep learning simple tutorial of running code
[literature reading] an investigation on hardware aware vision transformer scaling
Upload files to OSS file server
The place where the dream begins ---- first knowing C language (2)
4-4 对象生命周期
百度网址收录
About no module named'django.db.backends.mysql'
11_ Weather case - monitoring properties
[Gorm] model relationship -hasone
At 12:00 on July 17, 2022, the departure of love life on June 28 was basically completed, and it needs to rebound
Design of vision protector based on 51 single chip microcomputer
Transformers is a graph neural network