Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #### Zeinab
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define RV return void
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define cin(v) for(auto&x:v) cin >> x;
- #define cout(v) for(auto&x:v) cout << x << " ";
- int n ;
- vector < vector < int > > adj;
- int node , maxdepth , node_1 , node_2;
- vector < int > cnt ;
- void dfs(int u , int par , int dis){
- if(dis > maxdepth){
- maxdepth = dis;
- node = u;
- }
- cnt[u] = dis;
- for(auto& v : adj[u]){
- if(par != v){
- dfs(v , u , dis + 1);
- }
- }
- }
- set < int > worst ;
- void dfs2(int u , int par , int dis){
- if(dis == maxdepth){
- worst.insert(u);
- }
- for(auto& v : adj[u]){
- if(par != v){
- dfs2(v , u , dis + 1);
- }
- }
- }
- void solve(){
- while(cin >> n ){
- adj.assign(n+1 , vector < int > ());
- cnt.assign(n+1,0);
- for(int i =1 ; i <= n ; i++){
- int q , u ; cin >> q;
- while(q--){
- cin >> u;
- adj[i].pb(u);
- }
- }
- node = maxdepth =0;
- dfs(1 , -1 , 0);
- maxdepth =0;
- node_1 = node;
- node=0;
- cnt.assign(n+1,0);
- dfs(node_1 , -1 , 0);
- node_2 = node;
- cout << "Best Roots : ";
- if( maxdepth % 2 ==0){
- // 1 node
- for(int i =1 ; i <= n ; i++){
- cnt[i] = maxdepth - cnt[i] ;
- if(cnt[i] == maxdepth/2 and sz(adj[i]) > 1 ){
- cout << i << " ";
- }
- }
- }else{
- // 2 node
- for(int i =1 ; i <= n ; i++){
- cnt[i] = maxdepth - cnt[i] ;
- if((cnt[i] == maxdepth/2 or cnt[i] == maxdepth/2 + 1) and sz(adj[i]) > 1 ){
- cout << i << " ";
- }
- }
- }
- cout << nl;
- cout<<"Worst Roots : ";
- worst.clear();
- dfs2(node_1 , -1 , 0);
- dfs2(node_2 , -1 , 0);
- for(auto& x : worst){
- cout << x << " ";
- }
- cout << nl;
- }
- }
- int main(){
- ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
- int t=1;
- // cin >> t ;
- for(int i=1 ; i <= t ; i++){
- // cout << "Case "<< i <<": " ;
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement