当前位置:网站首页>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;
}
边栏推荐
- 【不积跬步无以至千里】统计日志指定时间段内的关键词
- 【面试:并发篇26:多线程:两阶段终止模式】volatile版本
- 证券公司哪家佣金最低?网上开户安全吗
- Part II - C language improvement_ 7. Structure
- 会议OA之我的会议
- 力扣141题:环形链表
- 文件上传到OSS文件服务器
- Dajiang Zhitu and CC have produced multiple copies of data. How to combine them into one and load them in the new earth map
- Question 141 of Li Kou: circular linked list
- 第二部分—C语言提高篇_8. 文件操作
猜你喜欢

嵌入式系统移植【8】——设备树和根文件系统移植

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

Chapter 7 course summary

Pytorch learning record (II): tensor

Part II - C language improvement_ 11. Pretreatment

数据库:MySQL基础+CRUD基本操作

Push to origin/master was rejected error resolution

Azure synapse analytics Performance Optimization Guide (4) -- optimize performance using result set caching

np. transpose & np.expand_ dims

Chapter 1 develop the first restful application
随机推荐
[Gorm] model relationship -hasone
04 traditional synchronized lock
[C language] array
Section 6: introduction to cmake grammar
12_ Binding style
Force deduction 155 questions, minimum stack
[C language] classic recursion problem
In simple terms, cchart's daily lesson - Lesson 59 of happy high school 4 comes to the same end by different ways, and the C code style of the colorful interface library
09_ Keyboard events
第二部分—C语言提高篇_6. 多维数组
07 design of ponding monitoring system based on 51 single chip microcomputer
Part II - C language improvement_ 5. Bit operation
Pytorch学习记录(二):张量
第1章 需求分析与ssm环境准备
Dynamic SQL
Simple SQL optimization
04-传统的Synchronized锁
Bid farewell to wide tables and achieve a new generation of Bi with DQL
Upload files to OSS file server
C语言数组