Samkit5025

Untitled

Jun 22nd, 2022
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 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