树是一种特殊的图结构,有根树是一个有固定根的树。

现在给定一棵有根树,编程求出树中所有节点到指定的根节点最远距离。

输入格式

第一行是两个整数 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;
}
分类: BFSDFSTree

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status