1090. Highest Price in Supply Chain (25)[dfs树的遍历]

本文主要是介绍1090. Highest Price in Supply Chain (25)[dfs树的遍历]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 原题： https://www.patest.cn/contests/pat-a-practise/1090

2. 思路：

题意：
给出一颗树，求出树的最大层次及同层的结点数。
思路：
显然可以用dfs，每次递归，层次加1.
也可用bfs.
为求简便，用dfs。
已AC

3. 源码：

#include<iostream>
#include<vector>
#include<algorithm>//使用pow函数，用来求指数
using namespace std;int level = 0, N;//分别为树的最大层次， 结点数
int cnt = 0;//同一层次的结点数
vector< vector<int> > G;//图的邻接表表示
void dfs(int root, int deep);//dfs递归求最大层次int main(void)
{//freopen("in.txt", "r", stdin);int root;//树的根double price, rate;//分别为初始价， 加价比率scanf("%d %lf %lf", &N, &price, &rate);G.resize(N);for (int i = 0; i < N; i++)//读入数据{int parent;//父结点编号scanf("%d", &parent);if (parent == -1)//找到了根结点root = i;elseG[parent].push_back(i);//压入父结点的容器}dfs(root, 0);//递归求出层次level和个数cntdouble max_price = price * pow((1 + rate / 100), double(level));//最高价printf("%.2f %d\n", max_price, cnt);return 0;
}void dfs(int root, int deep)//dfs递归求最大层次
{if (G[root].empty())//表示到了叶子结点，递归结束{if (level < deep)//更新树深和个数cnt{level = deep;cnt = 1;}else if (level == deep)cnt++;return;}for (int i = 0; i < G[root].size(); i++)//递归子树dfs(G[root][i], deep + 1);return;
}

这篇关于1090. Highest Price in Supply Chain (25)[dfs树的遍历]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！