Samkit5025

Untitled

Jun 22nd, 2022
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1.  
  2. import java.util.*;
  3.  
  4. class Pair{
  5. int ff;
  6. int ss;
  7. public Pair(int f,int s) {
  8. ff = f;
  9. ss = s;
  10. }
  11. }
  12.  
  13. class CustomSort implements Comparator<Pair>{
  14.  
  15. @Override
  16. public int compare(Pair a, Pair b) {
  17. if(a.ss!=b.ss) {
  18. return b.ss-a.ss;
  19. }
  20. return b.ff-a.ff;
  21. }
  22.  
  23. }
  24.  
  25.  
  26. public class Solution {
  27.  
  28. static Scanner sc = new Scanner(System.in);
  29.  
  30. public static void dfsUtil(ArrayList<Integer>[] A,int src,int par,int[] citiesCanBeVisited) {
  31. int ans = 0;
  32.  
  33. for(int i : A[src]) {
  34. if(i!=par) {
  35. dfsUtil(A,i,src,citiesCanBeVisited);
  36. ans+=(citiesCanBeVisited[i]+1);
  37. }
  38. }
  39. citiesCanBeVisited[src] = ans;
  40. }
  41.  
  42. public static ArrayList<Integer> orderProsperity(int N, ArrayList<Integer>[] A){
  43. ArrayList<Integer> result = new ArrayList<>();
  44.  
  45. int[] citiesVisited = new int[N+1];
  46. for(int i=0;i<=N;i++) {
  47. citiesVisited[i] = -1;
  48. }
  49.  
  50. Queue<Integer> q = new LinkedList<>();
  51. q.add(1);
  52. citiesVisited[1] = 0;
  53.  
  54. while(!q.isEmpty()) {
  55. int temp = q.remove();
  56. for(int i : A[temp]) {
  57. if(citiesVisited[i] == -1) {
  58. citiesVisited[i] = citiesVisited[temp]+1;
  59. q.add(i);
  60. }
  61. }
  62. }
  63.  
  64. int[] citiesCanBeVisited = new int[N+1];
  65. for(int i=0;i<=N;i++) {
  66. citiesCanBeVisited[i] = 0;
  67. }
  68.  
  69. dfsUtil(A,1,-1,citiesCanBeVisited);
  70.  
  71. ArrayList<Pair> dummy = new ArrayList<>();
  72.  
  73. for(int i=1;i<=N;i++) {
  74. dummy.add(new Pair(i,citiesCanBeVisited[i] * citiesVisited[i]));
  75. }
  76.  
  77. Collections.sort(dummy, new CustomSort());
  78.  
  79.  
  80. for(Pair i : dummy) {
  81. result.add(i.ff);
  82. }
  83.  
  84. return result;
  85. }
  86.  
  87. public static void main(String[] args) {
  88. int N;
  89. N = sc.nextInt();
  90.  
  91. ArrayList<Integer>[] A = new ArrayList[N+1];
  92.  
  93. for(int i=0;i<=N;i++) A[i] = new ArrayList<>();
  94.  
  95. for(int i=0;i<N-1;i++) {
  96. int temp1 = sc.nextInt();
  97. int temp2 = sc.nextInt();
  98.  
  99. A[temp1].add(temp2);
  100. A[temp2].add(temp1);
  101. }
  102.  
  103. ArrayList<Integer> result= orderProsperity(N,A);
  104.  
  105. for(int i : result) {
  106. System.out.print(i + " ");
  107. }
  108.  
  109. System.out.println();
  110. }
  111. }
  112.  
  113.  
  114.  
  115.  
Advertisement
Add Comment
Please, Sign In to add comment