洛谷 B2170：树上结点深度 ← DFS + 链式前向星

【题目来源】
https://www.luogu.com.cn/problem/B2170

【题目描述】
给定一棵包含 n 个结点的树，结点编号为 1∼n。我们将 1 号结点指定为这棵树的根。
定义根结点的深度为 1。对于任意非根结点 u，其深度定义为其父结点的深度加 1。
请你计算并输出这棵树中每个结点的深度。

【输入格式】
输入的第一行包含一个整数 n，表示树的结点个数。
接下来 n−1 行，每行包含两个整数 u,v，表示结点 u 和结点 v 之间存在一条无向边。保证输入的数据构成一棵树。​​​​​​​

【输出格式】
输出一行，包含 n 个整数。第 i 个整数表示编号为 i 的结点的深度。两个整数之间请用一个空格隔开。

【输入样例】
5
1 2
1 3
2 4
2 5​​​​​​​

【输出样例】
1 2 2 3 3

【数据范围】
对于 30% 的数据，满足 n≤100。
对于 60% 的数据，满足 n≤1000。
对于 100% 的数据，满足 1≤n≤500,000。保证输入的各条边能组成一棵含有 n 个结点的树。​​​​​​​

【算法分析】
● 链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
● 提升 cin/cout 速度：https://blog.csdn.net/hnjzsyjyj/article/details/143176072

【算法代码】

#include <bits/stdc++.h> using namespace std; const int N=5e5+5; int e[N<<1],ne[N<<1],h[N],idx; int dep[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa) { dep[u]=dep[fa]+1; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs(j,u); } } int main() { ios::sync_with_stdio(0); cin.tie(0); memset(h,-1,sizeof h); int n; cin>>n; for(int i=1; i<n; i++) { int x,y; cin>>x>>y; add(x,y),add(y,x); } dfs(1,0); for(int i=1; i<=n; i++) { cout<<dep[i]<<" "; } return 0; } /* in: 5 1 2 1 3 2 4 2 5 out: 1 2 2 3 3 */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160746347
https://blog.csdn.net/hnjzsyjyj/article/details/152726091
https://blog.csdn.net/hnjzsyjyj/article/details/152729089