Advertisement
Guest User

Untitled

a guest
Sep 18th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     ll n,x,y;
  9.     cin >> n;
  10.     vector<ll>g[n+1];
  11.     for(ll i = 0; i<n-1 ; i++){
  12.         cin >> x >> y;
  13.         g[x].push_back(y);
  14.         g[y].push_back(x);
  15.     }
  16.     vector<ll>vis(n+1);
  17.     vector<ll>dis(n+1);
  18.     ll src = g[1][0];
  19.     dis[src] = 0;
  20.     vis[src] = 1;
  21.     queue<ll> q;
  22.     q.push(src);
  23.     while(q.size() > 0){
  24.         ll x = q.front();            q.pop();
  25.         for(ll i = 0; i<g[x].size(); i++){
  26.             if(vis[g[x][i]] == 1)continue;
  27.             vis[g[x][i]] = 1;
  28.             dis[g[x][i]] = dis[x] + 1;
  29.             q.push(g[x][i]);
  30.  
  31.         }
  32.     }
  33.     ll max = -1;
  34.     ll index;
  35.  
  36.     for(ll i =0 ; i<dis.size(); i++){
  37.         if(dis[i] > max){
  38.             max = dis[i];
  39.             index = i;
  40.         }
  41.     }
  42.         vector<ll>vis1(n+1);
  43.     vector<ll>dis1(n+1);
  44.     src = index;
  45.     dis1[src] = 0;
  46.     vis1[src] = 1;
  47.     queue<ll> q1;
  48.     q1.push(src);
  49.     while(q1.size()){
  50.         ll x = q1.front();
  51.         q1.pop();
  52.         for(ll i = 0; i<g[x].size(); i++){
  53.             if(vis1[g[x][i]] == 1)continue;
  54.             vis1[g[x][i]] = 1;
  55.             dis1[g[x][i]] = dis1[x] + 1;
  56.             q1.push(g[x][i]);
  57.         }
  58.     }
  59.     for(ll i =0 ; i<dis.size(); i++){
  60.         if(dis1[i] > max){
  61.             max = dis1[i];
  62.             index = i;
  63.         }
  64.     }
  65.     cout << max << endl;
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement