题解 | #最多节点数#

题意整理

给定n个节点，n-1条边组成的无向连通图，有a、b两节点，分别位于1和x。
求a和b同时移动到同一节点所经过的最多的节点数（路径必须包括1）。

方法一（DFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
然后初始化dist1和dist2，分别记录某节点到1节点所经过的节点数、某节点到x节点所经过的节点数。
从1节点或者x节点开始递归，每到一个节点，遍历当前节点的所有未访问的子节点，跟新子节点对应的dist，继续递归，直到遍历完所有节点。

直接递归，会报栈深度溢出错误。可以通过自定义栈深度的方式解决。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多需要经过的节点数
     * @param n int 
     * @param x int 
     * @param Edge Point一维数组 
     * @return int
     */
    //邻接表
    List<List<Integer>> graph;
    //经过的节点数数组
    int[] dist1;
    int[] dist2;
    //节点个数
    int n;
    //结果变量
    int res;
    public int solve (int n, int x, Point[] Edge) {
        try{
            Thread t=new Thread(null,()->{
                maxNodeNum(n,x,Edge);
            },"自定义栈深度",1<<30);
            t.start();
            t.join();
        }
        catch(Exception e){

        }
        return res;
    }

    public void maxNodeNum (int n, int x, Point[] Edge) {
        //初始化节点个数和邻接表
        this.n=n;
        this.graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //初始化dist数组
        dist1=new int[n];
        dist2=new int[n];
        //赋初值
        dist1[0]=1;
        dist2[x-1]=1;
        //递归
        dfs(0,dist1);
        dfs(x-1,dist2);

        res=0;
        for(int i=0;i<n;i++){
            //当dist1[i]>dist2[i]时，求最大的dist1
            if(dist1[i]>dist2[i]){
                res=Math.max(res,dist1[i]);
            }
        }
    }

    //递归
    private void dfs(int i,int[] dist){
        for(Integer j:graph.get(i)){
            //遍历所有未访问过的子节点
            if(dist[j]==0){
                //增加对应节点数
                dist[j]=dist[i]+1;
                //往子节点方向递归
                dfs(j,dist);
            }

        }
    }
}

3.复杂度分析

时间复杂度：最坏情况下，需要访问所有的节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外深度为n的递归栈、大小为n的dist数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。

方法二（BFS）

1.解题思路

首先建立邻接表，用于访问某个节点的所有子节点。
然后初始化dist1和dist2，分别记录某节点到1节点所经过的节点数、某节点到x节点所经过的节点数。
每次从队列取出当前节点，遍历当前节点的所有子节点，如果子节点未被访问过，则给子节点的dist数组赋值，同时将该子节点入队，继续遍历。直到遍历完所有节点。

动图展示：
图片说明

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最多需要经过的节点数
     * @param n int 
     * @param x int 
     * @param Edge Point一维数组 
     * @return int
     */
    //邻接表
    List<List<Integer>> graph;
    //某节点到a节点路径上节点个数
    int[] dist1;
    //某节点到b节点路径上节点个数
    int[] dist2;
    //总节点个数
    int n;
    //结果变量
    int res;
    public int solve (int n, int x, Point[] Edge) {
        //初始化节点个数和邻接表
        this.n=n;
        this.graph=new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(Point point:Edge){
            int u=point.x;
            int v=point.y;
            graph.get(u-1).add(v-1);
            graph.get(v-1).add(u-1);
        }

        //初始化节点个数数组
        dist1=new int[n];
        dist2=new int[n];
        dist1[0]=1;
        dist2[x-1]=1;
        //广度优先遍历
        bfs(0,dist1);
        bfs(x-1,dist2);

        res=0;
        //因为必须包括1节点，所以取dist1的最大值
        for(int i=0;i<n;i++){
            if(dist1[i]>dist2[i]){
                res=Math.max(res,dist1[i]);
            }
        }

        return res;
    }

    //广度优先遍历
    public void bfs (int i,int[] dist) {
        //初始化队列
        Queue<int[] > queue=new LinkedList<>();
        queue.offer(new int[]{i,dist[i]});
        while(!queue.isEmpty()){
            //取出当前节点
            int[] node=queue.poll();
            int id=node[0];
            int d=node[1];
            //遍历所有子节点
            for(Integer j:graph.get(id)){
                if(dist[j]==0){
                    //如果未经过，加上对应数值，并添加到队列
                    dist[j]=d+1;
                    queue.offer(new int[]{j,dist[j]});
                }
            }
        }
    }
}

3.复杂度分析

时间复杂度：最多访问n个节点，所以时间复杂度为 $O(n)$ 。
空间复杂度：最坏情况下，需要额外大小为n的队列、大小为n的dist数组以及大小为 $n^2$ 的邻接表，所以空间复杂度为 $O(n^2)$ 。