Advertisement
Zeinab_Hamdy

Untitled

Aug 13th, 2024
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 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 ;
  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. void solve(){
  37.  
  38. while(cin >> n ){
  39.             adj.assign(n+1 , vector < int > ());
  40.             cnt.assign(n+1,0);
  41.            
  42.             for(int i =1 ; i <= n ; i++){
  43.                 int q , u ; cin >> q;
  44.                 while(q--){
  45.                     cin >> u;
  46.                     adj[i].pb(u);
  47.                 }
  48.             }
  49.  
  50.             node = maxdepth =0;
  51.             dfs(1 , -1 , 0);
  52.             // cout << node << " " << maxdepth << nl;
  53.             maxdepth =0;
  54.             cnt.assign(n+1,0);
  55.             dfs(node , -1 , 0);
  56.             // cout << node << " " << maxdepth << nl;
  57.            
  58.            
  59.             cout << "Best Roots : ";
  60.             if( maxdepth % 2 ==0){
  61.                 //  1 node
  62.                 for(int i =1 ; i <= n ; i++){
  63.                     cnt[i] = maxdepth - cnt[i] ;
  64.                     if(cnt[i] == maxdepth/2 and sz(adj[i]) > 1 ){
  65.                         cout << i << " ";
  66.                     }
  67.                 }
  68.             }else{
  69.                 //  2 node
  70.                 for(int i =1 ; i <= n ; i++){
  71.                     cnt[i] = maxdepth - cnt[i] ;
  72.                     // cout <<i << " " << cnt[i] << nl;
  73.                     if((cnt[i] == maxdepth/2 or cnt[i] ==  maxdepth/2 + 1) and sz(adj[i]) > 1 ){
  74.                         cout << i << " ";
  75.                     }
  76.                 }
  77.             }
  78.  
  79.             cout << nl;
  80.             cout<<"Worst Roots : ";
  81.             for(int i =1 ; i <= n ; i++){
  82.                 if(sz(adj[i]) == 1) {
  83.                     cout << i << " ";
  84.                 }
  85.             }
  86.             cout << nl;
  87.        
  88. }
  89.    
  90. }      
  91.  
  92.  
  93.  
  94. int main(){
  95.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  96.  
  97.     int t=1;
  98.         // cin >> t ;
  99.     for(int i=1 ; i <= t ; i++){
  100.         // cout << "Case "<< i <<": " ;
  101.         solve();
  102.     }
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement