首页 > 试题广场 >

则输出为( )

[单选题]

#include<bits/stdc++.h>
using namespace std;
vector<int>g[10];
int ans = 0;
void dfs(int x){
    if(g[x].size() == 0){
        ans++;
        return;
    }
    for(int i = 0; i < g[x].size(); ++i){
        dfs(g[x][i]);
    }
}
int main(){
    int n, x;
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i){
        scanf("%d", &x);
        g[x].push_back(i);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

上述程序的输入为：
9
1 2 2 1 5 6 6 6
则输出为(（）

```
4
```
```
5
```
```
6
```
```
7
```

查看正确选项

艾迪12346

输入之后的vector，g[1]={2,5},g[2]={3,4},g[5]={6},g[6]={7,8,9},其为空，ans在遇到空vector时会加1返回。从dfs（1）开始判断，g[1]不为空，判断g[1]内的元素，2和5，g[2]不为空，判断g[2]内部元素g[3]，g[4],均为空，ans进行两次加1，回到g[1]判断g[5],g[5]不为空，内部元素为6，判断g[6],g[6]不为空判断g[6]内部元素7,8,9，g[7],g[8],g[9]均为空，ans进行三次加1。结束，ans=5.

发表于 2019-11-05 22:03:31 回复(0)

我的天鸭

求的是树叶子结点的个数

发表于 2019-08-19 16:30:24 回复(2)

牛客166212013号

vector<int>g[10];是申明了一个是数组，其10个元素都是vector<int>。所以相当于g相当于一个二维数组。

经过输入

g[10][]={ {},

{2,5},

{3,4},

{},

{6},

{7,8,9},

{},

{}

}

if (g[x].size() == 0) 就是判断哪一行没有值

for (int i = 0; i < g[x].size(); ++i) 就是遍历当前行的所有元素。

经过迭代最终就是5

发表于 2020-08-11 23:32:55 回复(1)

好水告

这个push_back 函数作用不是把元素放在最后吗，这里答案的意思应该是就是对应着下标进行赋值吧。

发表于 2019-10-27 19:47:23 回复(3)

烬天玉藻前

想吐槽一下：代码可不可以缩进啊，看得有点难受，而且头文件也没包含<vector><iostream><stdio.h>勒。(好吧，我钻牛角尖了)

发表于 2020-08-20 22:36:26 回复(1)

不想打工的熊熊很安静

求叶子节点个数

编辑于 2023-12-07 12:04:58 回复(0)

一个达布刘

这道题就相当于把数组下标分别为1，2，5，6的数组内元素当做新下标看数组是否为空，为空就加1

发表于 2023-03-29 10:35:04 回复(0)

来个offer就签了呜呜呜呜

换成树来判断便很明显

发表于 2022-11-06 18:07:10 回复(0)

屏南吴彦祖

链接：https://www.nowcoder.com/questionTerminal/7ee25a9c9e964d42ac301e3d57407048?toCommentId=12248331
来源：牛客网
这道题我真人麻了，对vector有点忘记了。总结思路吧

首先可以把g想象成二维数组，i的范围是2~9也就是循环8次。
输入：1 2 2 1 5 6 6 6 也就是在g迭代器的坐标x：1里塞i也就是2，在坐标x：2里塞i也就是3……
g[1]的个数有2个，g[2]的个数有2个，g[5]的个数是1个，g[6]的个数是3个。也就是坐标2~9里有4个是有值的。
而函数（1）的循环，下标里有2和5，

调用函数（2）和函数（5），2里有3,4 5里有6
调用函数（3）和函数（4）和函数（6）……
总体来说就是判断迭代器下标1~9里没有添加值的下标个数

发表于 2022-03-23 12:05:50 回复(0)