Advertisement
Zeinab_Hamdy

Untitled

Aug 13th, 2024
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. //  #### Zeinab
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define nl "\n"
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ll long long
  9. #define RV return void
  10. #define sz(x) int(x.size())
  11. #define all(v) v.begin(), v.end()
  12. #define rall(v) v.rbegin(), v.rend()
  13. #define cin(v) for(auto&x:v) cin >> x;
  14. #define cout(v) for(auto&x:v) cout << x << " ";
  15.  
  16. int n ;
  17. vector < vector < int > > adj;
  18. int node , maxdepth  , node_1 , node_2;
  19. vector < int > cnt ;
  20.  
  21. void dfs(int u , int par , int dis){
  22.     if(dis > maxdepth){
  23.         maxdepth = dis;
  24.         node = u;
  25.     }
  26.  
  27.     cnt[u] = dis;
  28.  
  29.     for(auto& v : adj[u]){
  30.         if(par != v){
  31.             dfs(v , u , dis + 1);
  32.         }
  33.     }
  34. }
  35.  
  36. set < int > worst ;
  37.  
  38. void dfs2(int u , int par , int dis){
  39.     if(dis == maxdepth){
  40.         worst.insert(u);
  41.     }
  42.  
  43.     for(auto& v : adj[u]){
  44.         if(par != v){
  45.             dfs2(v , u , dis + 1);
  46.         }
  47.     }
  48. }
  49.  
  50.  
  51. void solve(){
  52.  
  53. while(cin >> n ){
  54.             adj.assign(n+1 , vector < int > ());
  55.             cnt.assign(n+1,0);
  56.            
  57.             for(int i =1 ; i <= n ; i++){
  58.                 int q , u ; cin >> q;
  59.                 while(q--){
  60.                     cin >> u;
  61.                     adj[i].pb(u);
  62.                 }
  63.             }
  64.  
  65.             node = maxdepth =0;
  66.             dfs(1 , -1 , 0);
  67.             maxdepth =0;
  68.             node_1 = node;
  69.             node=0;
  70.  
  71.             cnt.assign(n+1,0);
  72.             dfs(node_1 , -1 , 0);
  73.             node_2 = node;
  74.  
  75.  
  76.             cout << "Best Roots : ";
  77.             if( maxdepth % 2 ==0){
  78.                 //  1 node
  79.                 for(int i =1 ; i <= n ; i++){
  80.                     cnt[i] = maxdepth - cnt[i] ;
  81.                     if(cnt[i] == maxdepth/2 and sz(adj[i]) > 1 ){
  82.                         cout << i << " ";
  83.                     }
  84.                 }
  85.             }else{
  86.                 //  2 node
  87.                 for(int i =1 ; i <= n ; i++){
  88.                     cnt[i] = maxdepth - cnt[i] ;
  89.                     if((cnt[i] == maxdepth/2 or cnt[i] ==  maxdepth/2 + 1) and sz(adj[i]) > 1 ){
  90.                         cout << i << " ";
  91.                     }
  92.                 }
  93.             }
  94.  
  95.             cout << nl;
  96.             cout<<"Worst Roots : ";
  97.             worst.clear();
  98.             dfs2(node_1 , -1 , 0);
  99.             dfs2(node_2 , -1 , 0);
  100.            
  101.             for(auto& x : worst){
  102.                 cout << x << " ";
  103.             }
  104.             cout << nl;
  105.        
  106. }
  107.    
  108. }      
  109.  
  110.  
  111.  
  112. int main(){
  113.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  114.  
  115.     int t=1;
  116.         // cin >> t ;
  117.     for(int i=1 ; i <= t ; i++){
  118.         // cout << "Case "<< i <<": " ;
  119.         solve();
  120.     }
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement