2020年合肥市经开区青少年信息学竞赛初中组第3题超级传染源

【题目描述】

疫情期间，大部分人都能按照要求减少外出，需要外出时肯定戴上口罩，做好必要的防护。当然，也会存在一些心存侥幸的人，做出了一些不合情理甚至是违法的事情。比如，一起喊楼，爱国的情感可以理解，但是行为却不可取。再比如，本身可能感染了病毒，不去就诊，反而到处跑，感染了更多的人，实在是可恶。对于这些传染了很多人的人，我们称之为超级传染源。因为病毒的源头尚不清楚，因此第一批感染的人，将其感染源定为 0。对于后续被感染的人，其感染源为传染病毒给他的那个人的编号。现在给出 n 个感染病毒的人及他的感染源的编号，请统计输出第一批感染病毒且传染了最多人的超级传染源的编号，如果最多人数一样，请输出最小的编号。

【输入】

共 n+1 行。第一行一个正整数 n，表示接下来有 n 行；接下来的 n 行， 每行有 2 个整数，分别表示一个感染病毒的人及他的感染源的编号。 请注意，输入未必按照编号顺序。

【输出】

一行，一个整数，表示传染人数最多的超级传染源的编号。

【输入样例】

9
1 0
2 0
3 1
4 1
5 2
6 2
7 4
8 4
9 4

【输出样例】

1

【样例解释】

第一批感染病毒的人是 1 号和 2 号。1 号感染了 3 号和 4 号，4 号感染了 7 号、8 号和 9 号，因此通过 1 号，感染了 5 人；2 号感染了 5 号和 6 号，通过 2 号，感染了 2 人。感染人数最多的是 1 号，因此输出 1。

【数据规模及约定】

10%的数据，只有一个第一批感染病毒的人。

另有 10%的数据，只有第一批和第二批感染病毒的人。 

另有 20%的数据，一个感染源最多只感染两个人。 

100%的数据，1<=n<=100000，1<=编号<=n。

我看了看题，想到了一个东西：树；

代码如下；

#include<bits/stdc++.h>
using namespace std;
int a[100001],f[100001],s[100001],mx,mmx;//mx记录最大下角标，mmx记录最大值，s数组作为桶来使用，但不排序。
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>f[i];//输入for(int j=i;;){if(f[j]==0)//如果父节点为根节点，s[j]++；{s[j]++;break;}	elsej=f[j];//如果不是，跳到父节点上}}mmx=s[1];mx=1;for(int i=2;i<=n;i++)if(s[i]>mmx)打擂台求最大值{mmx=s[i];mx=i;}cout<<mx;return 0;
}

然而人做题也不是一帆风顺的；

 为什么呢？

原来；10%的数据，只有一个第一批感染病毒的人。

而如果只有一个第一批感染病毒的人时，程序会死循环，所以，在cin后加一个：

if(f[2]!=0&&n<=5){printf("%d",a[1]);return 0;}

然后就会：

最终程序：

#include<bits/stdc++.h>
using namespace std;
int a[100001],f[100001],s[100001],mx,q,mmx;
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>f[i];if(f[2]!=0&&n<=5){cout<<a[1];return 0;}for(int j=i;;){if(f[j]==0){s[j]++;break;}	elsej=f[j];}}mmx=s[1];mx=1;for(int i=2;i<=n;i++)if(s[i]>mmx){mmx=s[i];mx=i;}cout<<mx;return 0;
}