题解 | #最多节点数#

思路：

题目的主要信息：

n个节点n-1条边的无向连通图，即一棵无向树
两个节点a与b，其中a在节点1，b在节点x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数，需要包括1号节点在内

方法一：dfs
具体做法：
我们可以使用两次dfs分别求得树中每个节点到节点1和节点x的距离，然后遍历找到包含节点1的最大距离即是所经过的最多节点数。
dfs时我们采用递归，子节点距离等于父节点距离加1，然后递归遍历该节点的所有子节点（不能是父节点）。

class Solution {
public:
    void dfs(int cur, int pre, vector<int>& dis, vector<vector<int>>& G){
        dis[cur] = dis[pre] + 1; //子节点距离等于父节点距离加1
        for(int i = 0; i < G[cur].size(); i++){
            if(G[cur][i] != pre)
                dfs(G[cur][i], cur, dis, G);
        }
    }
    int solve(int n, int x, vector<Point>& Edge) {
        int res = 0;
        vector<int> dis1(n + 1, 0);
        vector<int> disx(n + 1, 0);
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < Edge.size(); i++){ //构建图
            G[Edge[i].x].push_back(Edge[i].y);
            G[Edge[i].y].push_back(Edge[i].x);
        }
        dfs(1, 0, dis1, G); //记录其他节点到1的距离
        dfs(x, 0, disx, G); //记录其他节点到x的距离
        for(int i = 1; i <= n; i++)
            if(dis1[i] > disx[i]) //找到最大的节点数，包括1在内
                res = max(res, dis1[i]);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历每一个节点，后面找最大值也是 $O(n)$
空间复杂度： $O(n)$ ，辅助矩阵G最多有 $2n$ 个元素

方法二：bfs
具体做法：
我们也可以从节点1和节点x分别做bfs，记录每一层的距离，遍历每一个节点，即可得到方法一中的到所有节点到节点1和节点x的距离。然后像方法一一样遍历寻找最大值。
bfs的时候是从节点1或者节点x出发，因此需要初始化为这个点的距离为1，然后借助队列，将节点和距离作为pair入队，便可以在bfs的时候距离跟着走，同一层的距离相同，只要用到了子节点进入下一层，距离就会增加1.用距离为0表示还未访问过该节点。
图片说明

class Solution {
public:
    void bfs(int cur, vector<int>& dis, vector<vector<int>>& G){
        queue<pair<int, int> > q;
        q.push(make_pair(cur, dis[cur])); //节点和距离要求的节点数入队
        while(!q.empty()){ //bfs
            int node = q.front().first;
            int dist = q.front().second;
            q.pop();
            for(int i = 0; i < G[node].size(); i++){
                if(dis[G[node][i]] == 0){ //没有访问过
                    dis[G[node][i]] = dist + 1;
                    q.push(make_pair(G[node][i], dis[G[node][i]]));
                }
            }
        }
    }
    int solve(int n, int x, vector<Point>& Edge) {
        int res = 0;
        vector<int> dis1(n + 1, 0);
        vector<int> disx(n + 1, 0);
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < Edge.size(); i++){ //构建图
            G[Edge[i].x].push_back(Edge[i].y);
            G[Edge[i].y].push_back(Edge[i].x);
        }
        dis1[1] = 1;
        disx[x] = 1; //初始化1和x这两个点
        bfs(1, dis1, G); //记录其他节点到1的距离
        bfs(x, disx, G); //记录其他节点到x的距离
        for(int i = 1; i <= n; i++)
            if(dis1[i] > disx[i]) //找到最大的节点数，包括1在内
                res = max(res, dis1[i]);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历每一个节点，后面找最大值也是 $O(n)$
空间复杂度： $O(n)$ ，辅助矩阵G最多有 $2n$ 个元素，辅助队列长度最大为 $n$