当前位置:网站首页>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;
}
边栏推荐
- Can the stock account opening commission be adjusted? Is it safe to open an account on your mobile phone
- Dajiang Zhitu and CC have produced multiple copies of data. How to combine them into one and load them in the new earth map
- Tencent cloud lightweight application server purchase method steps!
- Design of electronic scale based on 51 single chip microcomputer
- Azure Synapse Analytics 性能优化指南(3)——使用具体化视图优化性能(下)
- Everything you should know about wearable NFT!
- New features of ES6
- C语言数组
- 12_ Binding style
- 2022.7.18-----leetcode.749
猜你喜欢

Method of realizing program startup and self startup through registry

Part II - C language improvement_ 9. Linked list
![[Gorm] model relationship -hasone](/img/90/3069059ddd09dc538c10f76d659b08.png)
[Gorm] model relationship -hasone

第二部分—C语言提高篇_12. 动/精态库的封装和使用

Pytorch learning record (II): tensor

MVC three-tier architecture
![[C language] array](/img/b7/fe090984af689e45cf3492ff8d4c61.png)
[C language] array

上千Tile的倾斜模型浏览提速,告别一块一块往外蹦的尴尬

About no module named'django.db.backends.mysql'

4-4 对象生命周期
随机推荐
14_ Basic list
Azure synapse analytics Performance Optimization Guide (3) -- optimize performance using materialized views (Part 2)
Chapter 1 Introduction and use skills of interceptors
Method of realizing program startup and self startup through registry
12_ Binding style
NFT展示指南:如何展示你的NFT藏品
MVC三层架构
【面试:并发篇27:多线程:犹豫模式】
[netding Cup 2018] Fakebook records
Part II - C language improvement_ 10. Function pointer and callback function
Galaxy securities online account opening commission, is online account opening safe for customer managers
会议OA之我的会议
Thousands of tiles' tilt model browsing speeds up, saying goodbye to the embarrassment of jumping out one by one
How to transfer the GPX data collected by CTI RTK out of KML and SHP with attributes for subsequent management and analysis
10_ Name Case - Calculation attribute
告别宽表,用 DQL 成就新一代 BI
Recent answers - column
Bid farewell to wide tables and achieve a new generation of Bi with DQL
Complete backpack and 01 Backpack
Hcip day 2_ HCIA review comprehensive experiment