Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int dfsUtil(map<int,vector<int>> &hm,int src,int par,vector<int> &citiesCanBeVisited){
- int ans = 0;
- for(int i : hm[src]){
- if(i!=par){
- ans+=dfsUtil(hm,i,src,citiesCanBeVisited);
- }
- }
- citiesCanBeVisited[src] = ans;
- return ans+1;
- }
- vector<int> orderProsperity(int N, map<int,vector<int>> &hm){
- vector<int> result;
- vector<int> citiesVisted(N+1,-1);
- queue<int> q;
- q.push(1);
- int count =0;
- while(!q.empty()){
- int len = q.size();
- for(int i=0;i<len;i++){
- int tempCity = q.front();
- q.pop();
- citiesVisted[tempCity] = count;
- for(int j : hm[tempCity]){
- if(citiesVisted[j]==-1){
- q.push(j);
- }
- }
- }
- count++;
- }
- vector<int> citiesCanBeVisited(N+1,0); // to count the number of citites in the sunnetwork
- dfsUtil(hm,1,-1,citiesCanBeVisited);
- vector<pair<int,int>> dummy;
- for(int i=1;i<=N;i++){
- dummy.push_back({i,citiesVisted[i] * citiesCanBeVisited[i]});
- }
- sort(dummy.begin(),dummy.end(),[](pair<int,int> &a,pair<int,int> &b){
- if(a.second != b.second)return a.second>b.second;
- return a.first>b.first;
- });
- for(auto i : dummy){
- result.push_back(i.first);
- }
- return result;
- }
- int main(){
- int N;
- cin >> N;
- map<int,vector<int>> hm;
- for(int i=0;i<N-1;i++){
- int a,b;
- cin>>a>>b;
- hm[a].push_back(b);
- hm[b].push_back(a);
- }
- vector<int> ans = orderProsperity(N,hm);
- for(int i : ans){
- cout<<i<<" ";
- }
- cout<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment