第三题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) 回帖