#广度优先遍历之树的高度#南京理工大学机试

https://www.acwing.com/problem/content/3702/

思路：本题明面上是求树的高度，但却给出了类似于邻接表的存储方式，类似于一张无环图，但完全不知道节点之间的父子关系。考虑两种搜索方式，层序遍历可以严格保证先父后子的遍历顺序，故采用层序遍历。同时设置一个辅助数组来记录节点是否被访问过，如有，则证明是当前节点的父辈。

做法：分别定义一个vector<vector<int>>型的邻接表结构，一个存储遍历顺序的队列toVisit，一个记录是否访问和最大长度的数组distance，循环访问邻接表。初始将固定的根节点压入队列。当队列不为空时：

1.读取队首元素并出队

2.遍历队首元素所对应的vector，对于每一个节点：

a.若对应distance值不为-1，跳过

b.若为-1，证明尚未被访问。将该节点压入队列末尾，同时将distance设为从根到当前节点的父节点的值＋1，并更新max

3.直到循环退出，打印max即可

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    int max=0;
    scanf("%d%d",&n,&m);
    vector<vector<int>> table(n+1);
    for(int i=0;i<n-1;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        table[u].push_back(v);
        table[v].push_back(u);
    }
    queue<int> toVisit;
    vector<int> distance(n+1);
    for(int i=1;i<=n;++i) distance[i] = -1;
    distance[m]=0;
    toVisit.push(m);

    while(!toVisit.empty()){
        int current = toVisit.front();
        toVisit.pop();

        for(int i=0;i<table[current].size();i++){
            int child = table[current][i];
            if(distance[child] != -1){
                continue;
            }
            toVisit.push(child);
            distance[child] = distance[current] + 1;
            max=distance[child];
        }
    }
    printf("%d\n",max);
    return 0;
}