Samkit5025

Untitled

Jun 18th, 2022
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.77 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dfsUtil(map<int,vector<int>> &hm,int src,int par,vector<int> &citiesCanBeVisited){
  5. int ans = 0;
  6.  
  7. for(int i : hm[src]){
  8. if(i!=par){
  9. ans+=dfsUtil(hm,i,src,citiesCanBeVisited);
  10. }
  11. }
  12.  
  13. citiesCanBeVisited[src] = ans;
  14. return ans+1;
  15. }
  16.  
  17. vector<int> orderProsperity(int N, map<int,vector<int>> &hm){
  18. vector<int> result;
  19.  
  20. vector<int> citiesVisted(N+1,-1);
  21.  
  22. queue<int> q;
  23. q.push(1);
  24.  
  25. int count =0;
  26.  
  27. while(!q.empty()){
  28. int len = q.size();
  29.  
  30. for(int i=0;i<len;i++){
  31. int tempCity = q.front();
  32. q.pop();
  33.  
  34. citiesVisted[tempCity] = count;
  35. for(int j : hm[tempCity]){
  36. if(citiesVisted[j]==-1){
  37. q.push(j);
  38. }
  39. }
  40. }
  41.  
  42. count++;
  43. }
  44.  
  45. vector<int> citiesCanBeVisited(N+1,0); // to count the number of citites in the sunnetwork
  46.  
  47. dfsUtil(hm,1,-1,citiesCanBeVisited);
  48.  
  49. vector<pair<int,int>> dummy;
  50. for(int i=1;i<=N;i++){
  51. dummy.push_back({i,citiesVisted[i] * citiesCanBeVisited[i]});
  52. }
  53.  
  54. sort(dummy.begin(),dummy.end(),[](pair<int,int> &a,pair<int,int> &b){
  55. if(a.second != b.second)return a.second>b.second;
  56. return a.first>b.first;
  57. });
  58.  
  59. for(auto i : dummy){
  60. result.push_back(i.first);
  61. }
  62.  
  63. return result;
  64. }
  65.  
  66. int main(){
  67.  
  68. int N;
  69. cin >> N;
  70.  
  71. map<int,vector<int>> hm;
  72.  
  73. for(int i=0;i<N-1;i++){
  74. int a,b;
  75. cin>>a>>b;
  76.  
  77. hm[a].push_back(b);
  78. hm[b].push_back(a);
  79. }
  80.  
  81. vector<int> ans = orderProsperity(N,hm);
  82.  
  83. for(int i : ans){
  84. cout<<i<<" ";
  85. }
  86.  
  87. cout<<endl;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment