首页 > 美团8.29AC情况统计
头像
CadmusJiang
编辑于 2020-08-29 17:57
+ 关注

美团8.29AC情况统计 投票

第三题ac代码
class Solution{
    private Map<Integer,Set<Integer>> links = new HashMap<>();
    private Map<Integer,Integer> dis = new HashMap<>();
    public void solution(int n,int x,int y,int[][] area){
        if(x==y){
            System.out.println(0);
            return;
        }
        boolean[] vis = new boolean[n];
        for(int i=0;i<area.length;i++){
            Set<Integer> set1 = links.getOrDefault(area[i][0],new HashSet<>());
            set1.add(area[i][1]);
            links.put(area[i][0],set1);
            Set<Integer> set2 = links.getOrDefault(area[i][1],new HashSet<>());
            set2.add(area[i][0]);
            links.put(area[i][1],set2);
        }
        // 从x出发到达所有点需要的时间
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        vis[x-1] =true;
        int dep = 0;
        while(!queue.isEmpty()){
            int size =  queue.size();
            for(int i=0;i<size;i++){
                int tmp  = queue.poll();
                dis.put(tmp,dep);
                Set<Integer> set = links.get(tmp);
                for(Integer val : set){
                    if(vis[val-1]==false){
                        queue.add(val);
                        vis[val-1] = true;
                    }

                }
            }
            dep++;
        }
        //从y出发 在不碰到x的情况下最远的点
        vis = new boolean[n];
        int max = 0;
        queue = new LinkedList<>();
        queue.offer(y);
        vis[y-1]=true;
        dep = 0;
        while(!queue.isEmpty()){
            int size =  queue.size();
            for(int i=0;i<size;i++){
                int tmp  = queue.poll();
                if(dis.get(tmp)>max){
                    max = dis.get(tmp);
                }
                Set<Integer> set = links.get(tmp);
                for(Integer val : set){
                    if(vis[val-1]==false&&dis.get(val)>dep+1){
                        queue.add(val);
                        vis[val-1] = true;
                    }
                }
            }
            dep++;
        }
        System.out.println(max);
    }
}
public class Main {
    public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int[][] links = new int[n - 1][2];
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < 2; j++) {
                    links[i][j] = scanner.nextInt();
                }
            }
            Solution solution = new Solution();
            solution.solution(n, x, y, links);
    }
}
然后***的都是弟弟

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐