AcWing 3699：树的高度 ← BFS + 邻接表

​【题目来源】
https://www.acwing.com/problem/content/3702/

【题目描述】
树是一种特殊的图结构，有根树是一个有固定根的树。
现在给定一棵有根树，编程求出树中所有节点到指定的根节点最远距离。

【输入格式】
第一行是两个整数 N,M，表示数的顶点数和根节点的编号。
接下来 N−1 行，每行两个整数 u,v，表示编号为 u 的节点和编号为 v 的节点间有一无向条边。

【输出格式】
输出距离根节点最远的点到根的距离。

【数据范围】
1≤N≤10000,
1≤M≤N,
1≤u,v≤N

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

【输出样例】
3

【算法分析】
本题的“链式前向星”实现：https://blog.csdn.net/hnjzsyjyj/article/details/152729089

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=1e4+5;
vector<int> g[N];
int dep[N];
int n,m,ans;void bfs(int rt) {memset(dep,-1,sizeof dep);queue<int> q;q.push(rt);dep[rt]=0;while(!q.empty()) {int u=q.front();q.pop();for(int v:g[u]) {if(dep[v]==-1) {dep[v]=dep[u]+1;ans=max(ans,dep[v]);q.push(v);}}}
}int main() {cin>>n>>m;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}bfs(m);cout<<ans<<endl;return 0;
}/*
in:
5 5
1 2
1 4
1 5
2 3out:
3
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/152729089
https://blog.csdn.net/hnjzsyjyj/article/details/152726091
https://www.acwing.com/solution/content/196325/
https://www.acwing.com/solution/content/224027/

 

​

​