Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Solution {
- static Scanner sc = new Scanner(System.in);
- public static ArrayList<Integer> athleticRace(int N,int M,ArrayList<Integer>[] A){
- ArrayList<Integer> result = new ArrayList<>();
- int[] time = new int[M+1];
- for(int i=1;i<=M;i++) {
- time[i] = -1;
- }
- Queue<Integer> q = new LinkedList<>();
- q.add(M);
- time[M] = 0;
- while(!q.isEmpty()) {
- int temp = q.remove();
- for(int i : A[temp]) {
- if(time[i] == -1) {
- time[i] = time[temp]+1;
- q.add(i);
- }
- }
- }
- int max_time = 0;
- HashSet<Integer> hs = new HashSet<>();
- for(int i=1;i<=N;i++) {
- hs.add(time[i]);
- if(max_time < time[i]) {
- max_time = time[i];
- }
- }
- if(hs.size() == 1) {
- result.add(-1);
- return result;
- }
- for(int i=1;i<=N;i++) {
- if(max_time == time[i]) {
- result.add(i);
- }
- }
- return result;
- }
- public static void main(String[] args) {
- int N,M;
- N = sc.nextInt();
- M = sc.nextInt();
- ArrayList<Integer>[] A = new ArrayList[M+1];
- for(int i=0;i<=M;i++) {
- A[i] = new ArrayList<>();
- }
- for(int i = 0;i<M-1;i++) {
- int temp1 = sc.nextInt();
- int temp2 = sc.nextInt();
- A[temp1].add(temp2);
- A[temp2].add(temp1);
- }
- ArrayList<Integer> result = athleticRace(N,M,A);
- for(int i : result) {
- System.out.print(i + " ");
- }
- System.out.println();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement