Advertisement
saurav_kalsoor

Untitled

Jun 22nd, 2022
993
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.73 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Solution {
  4.    
  5.     static Scanner sc = new Scanner(System.in);
  6.  
  7.    
  8.     public static ArrayList<Integer> athleticRace(int N,int M,ArrayList<Integer>[] A){
  9.         ArrayList<Integer> result = new ArrayList<>();
  10.        
  11.         int[] time = new int[M+1];
  12.        
  13.         for(int i=1;i<=M;i++) {
  14.             time[i] = -1;
  15.         }
  16.        
  17.         Queue<Integer> q = new LinkedList<>();
  18.         q.add(M);
  19.         time[M] = 0;
  20.        
  21.         while(!q.isEmpty()) {
  22.             int temp = q.remove();
  23.            
  24.             for(int i : A[temp]) {
  25.                 if(time[i] == -1) {
  26.                     time[i] = time[temp]+1;
  27.                     q.add(i);
  28.                 }
  29.             }
  30.         }
  31.        
  32.         int max_time = 0;
  33.         HashSet<Integer> hs = new HashSet<>();
  34.        
  35.         for(int i=1;i<=N;i++) {
  36.             hs.add(time[i]);
  37.             if(max_time < time[i]) {
  38.                 max_time = time[i];
  39.             }
  40.         }
  41.        
  42.         if(hs.size() == 1) {
  43.             result.add(-1);
  44.             return result;
  45.         }
  46.        
  47.         for(int i=1;i<=N;i++) {
  48.             if(max_time == time[i]) {
  49.                 result.add(i);
  50.             }
  51.         }
  52.        
  53.         return result;
  54.     }
  55.    
  56.     public static void main(String[] args) {
  57.         int N,M;
  58.         N = sc.nextInt();
  59.         M = sc.nextInt();
  60.        
  61.         ArrayList<Integer>[] A = new ArrayList[M+1];
  62.         for(int i=0;i<=M;i++) {
  63.             A[i] = new ArrayList<>();
  64.         }
  65.        
  66.         for(int i = 0;i<M-1;i++) {
  67.             int temp1 = sc.nextInt();
  68.             int temp2 = sc.nextInt();
  69.            
  70.             A[temp1].add(temp2);
  71.             A[temp2].add(temp1);
  72.         }
  73.        
  74.         ArrayList<Integer> result = athleticRace(N,M,A);
  75.        
  76.         for(int i : result) {
  77.             System.out.print(i + " ");
  78.         }
  79.         System.out.println();
  80.     }
  81. }
  82.  
  83.  
  84.  
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement