本文主要是介绍登山小分队（dfs，模拟），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：
题目描述
Foxity和他的好友们相约去爬山，但是他们每个人都来到了不同的山脚下。整个山的结构类似一棵 "树"，有很多的观光节点通过一条条山道连接起来。
在图论中，树是一种无向图，其中任意两个顶点之间存在唯一一条路径。或者说，只要没有回路的连通图就是树。这个问题中，我们将山顶视作树的根节点，而山脚视为树的叶节点，上山的每一条路可以视作树的一条边。
由于上山的道路年久失修，每条道路在同一时刻只能容纳一个人，而通过一条道路需要花费 111 时间。
现在他们分散在各个山脚（每个山脚恰好有一个人），现在他们想要知道最快的情况下，从现在到最后一个人登上山顶总共要花费多久的时间。
输入描述:
第一行一个整数 n(1≤n≤1000)n(1 \le n \le 1000)n(1≤n≤1000),表示总共节点的数量。接下来 n−1n-1n−1 行，每行两个整数，分别是 xi,yi(1≤xi,yi≤n)x_i,y_i(1 \le x_i,y_i \le n)xi,yi(1≤xi,yi≤n)，表示有一条路连接 xix_ixi 号点 和 yiy_iyi 号点，其中 111 号点即为山顶，保证给定的图是一棵树。
输出描述:
输出一行一个数，表示所有人都到齐的最少时间。
示例1
输入
复制3 1 2 1 3
3 1 2 1 3
输出
复制1
1
示例2
输入
复制4 1 2 2 3 2 4
4 1 2 2 3 2 4
输出
复制3
3
思路：
1，这个题真的没什么思路
2，要求每次一条路只能走一人，所有人走到1节点的最短时间
3，这个题最难的是，单个节点记录数量，dfs深度搜索，递归的书写
代码：
int num[1100];
vector<int>g[1100];
void dfs(int z,int fa){for(int i=0;i<g[z].size();++i){int y=g[z][i];if(y==fa)continue;//防止重复遍历if(num[y]){//模拟走的过程num[z]++;num[y]--;}dfs(y,z);//遍历子节点}
}
signed main(){//dfs模拟每一秒的动作int n;cin>>n;rep(i,1,n-1){int x,y;cin>>x>>y;g[x].emplace_back(y);//无向图g[y].emplace_back(x);}int sum=0;rep(i,2,n){if(g[i].size()==1)sum++,num[i]=1;//记录单个节点的}int ans=0;while(num[1]!=sum){//模拟每一秒，在一条路上能走则走dfs(1,1);ans++;}cout<<ans<<'\n';return 0;
}这篇关于登山小分队（dfs，模拟）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
