题目描述

n个节点n-1条边的无向连通图，两个点a，b，a位于1，b位于x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数。
输入
第一个参数为 n ，(1≤n≤100,000)
第二个参数为 x ，(1≤x≤n)
第三个参数为大小为 n−1 的点对 的集合，其中 表示结点ui与结点vi
之间有一条边，1≤ui,vi≤n
返回
最多需要经过的节点数（包括 1 号节点在内）
示例1
输入：5,2,[(1,2),(2,3),(3,4),(2,5)]
返回值：4

题目分析

连通图的概念是图中的任意两点之间都能有路径到达，当n个结点只有n-1条边形成的连通图一定是树状的，题目设定两个点a,b，a点固定从1出发，b点会从给定的x处出发，要想两点移动到同一点，可以获取从1到所有其他结点的距离dis1[]以及从x到其他结点的距离dis2[]，求同一点的dis1[i]和dis2[i]的移动结点数，因为一定要包括1号结点，所以考虑dis1[i]中的最大结点数。
图片说明

解题思路

方法1：DFS遍历整个树，获取每个结点到1和x的结点距离
dfs的思路比较直观：
1.创建邻接表graph，根据Edge数组初始化邻接表，创建结点数组dis1和dis2来记录到某个结点经过的结点数；
2.可以根据dis[i]是否为0 来标记结点是否已经访问过；
3.dfs从根开始遍历，访问根的子节点（邻接表），每经过一个结点，都要增加一个结点数；
4.遍历dis1和dis2，求出到i结点的最大结点数。

方法2：BFS遍历整个树，获取每个结点到1和x的结点距离
dfs遍历会需要较多的栈空间，一旦超过设定的栈深度，就会报栈溢出错误，使用bfs可以避免；

代码实现

方法1：DFS（会报栈溢出错误）

    //邻接表
    List<List<Integer>> graph;
    // 从1结点到某结点路径上结点的个数
    int[] dis1;
    // 从x结点到某结点路径上结点的个数
    int[] dis2;
    public int solve (int n, int x, Point[] Edge) {
        // 初始化邻接表
        graph = new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<Edge.length;i++){
            int u = Edge[i].x-1;
            int v = Edge[i].y-1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        // 初始化结点数组
        dis1 = new int[n];
        dis2 = new int[n];
        // 初始化1到1（下标对应0）的距离为1
        dis1[0] = 1;
        // 初始化x到x（下标对应x-1）的距离为1
        dis2[x-1] = 1;
        // dfs递归遍历，获得从1结点到其他路径上结点的个数
        dfs(0, dis1);
        // dfs递归遍历，获得从x结点到其他路径上结点的个数
        dfs(x-1, dis2);
        int res = 0;
        for(int i=0;i<n;i++){
            if(dis1[i] > dis2[i]){
                res = Math.max(res, dis1[i]);
            }
        }
        return res;
    }
    public void dfs(int i, int[] dis){
        for(Integer next:graph.get(i)){
            // 从i到next结点未初始化，则未经过
            if(dis[next] == 0){
                // 到next经过了一个i结点
                dis[next] = dis[i] + 1;
                dfs(next, dis);
            }
        }
    }

时间复杂度：，首先需要创建长度为n的邻接表，同时也要遍历Query数组，在dfs的过程中，在每个结点都只有一个子节点的情况下，递归深度达到最大n，所以花费的总时间为n级别；
空间复杂度：，空间上需要2(n-1)来存邻接结点（n个结点的树有n-1条边，边上的两个结点都会在邻接表中重复出现，所以是2(n-1)），还需要深度最大为n的递归栈空间，因为栈深度的限制，使用dfs时会报栈溢出错误；

方法2：BFS（借助队列，避免栈溢出）

    //邻接表
    List<List<Integer>> graph;
    // 从1结点到某结点路径上结点的个数
    int[] dis1;
    // 从x结点到某结点路径上结点的个数
    int[] dis2;
    public int solve (int n, int x, Point[] Edge) {
        // 初始化邻接表
        graph = new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<Edge.length;i++){
            int u = Edge[i].x-1;
            int v = Edge[i].y-1;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        // 初始化结点数组
        dis1 = new int[n];
        dis2 = new int[n];
        // 初始化1到1（下标对应0）的距离为1
        dis1[0] = 1;
        // 初始化x到x（下标对应x-1）的距离为1
        dis2[x-1] = 1;
        // dfs递归遍历，获得从1结点到其他路径上结点的个数
        bfs(0, dis1);
        // dfs递归遍历，获得从x结点到其他路径上结点的个数
        bfs(x-1, dis2);
        int res = 0;
        for(int i=0;i<n;i++){
            if(dis1[i] > dis2[i]){
                res = Math.max(res, dis1[i]);
            }
        }
        return res;
    }
    public void bfs(int i, int[] dis){
        //借助队列
        Queue<int[]> queue=new LinkedList<>();
        // 队列中存储结点和结点距离
        queue.offer(new int[]{i,dis[i]});
        while(!queue.isEmpty()){
            // 取出当前节点
            int[] node=queue.poll();
            int id=node[0];
            int d=node[1];
            // 遍历所有邻结点
            for(Integer next:graph.get(id)){
                if(dis[next]==0){
                    // 当还有子节点时，放入队列中，且距离加上该结点
                    dis[next]=d+1;
                    queue.offer(new int[]{next,dis[next]});
                }
            }
        }
    }

时间复杂度：，与dfs类似需要遍历数组，bfs使用的队列，省掉了递归的栈时间，增加了遍历邻接表的时间，时间复杂度为n级别；
空间复杂度：，与dfs相似，减少了栈空间，增加了队列来存储结点值，空间复杂度级别为n。