树的高度-南京理工大学

转载

2023 年 08 月 06 日

469 次浏览

暂无评论

1503字数

算法类

[来自KeChang](https://blog.silvery.me/)

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

### 输入格式

第一行是两个整数 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
```

### 题目分析

直接BFS即可。

### 代码实现

```
#include <iostream>
#include <queue>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;

int n, m, h[N], ne[N], e[N], idx, ans;
inline void push(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs(int node) {
    bool t = 0, flag = 0;
    int cls = 0;
    bitset <N> bt;
    queue <int> que[2];
    que[t].push(node);
    bt[node] = 1;
    while(que[t].size() || que[!t].size()) {
        while(que[t].size()) {
              auto u = que[t].front(); que[t].pop();
              for (int i = h[u]; ~i; i = ne[i]) {
                  auto& buf = e[i];
                  if (!bt[buf]) {
                      flag = true;
                      bt[buf] = 1;
                      que[!t].push(buf);
                  }
              }
        }
        if (flag) ++cls;
        flag = false;
        t = !t;
    }
    return cls;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(n--) {
        int u, v;
        cin >> u >> v;
        push(u,v), push(v,u);
    }
    cout << bfs(m);
    return 0;
}
```

最后修改：2023 年 08 月 06 日