Advertisement
Josif_tepe

Untitled

Oct 12th, 2023
812
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. const int maxn=500000;
  6. vector<int> graph[maxn];
  7. pair<int, int> bfs(int S) {
  8.     queue<int> q;
  9.     q.push(S);
  10.     q.push(0);
  11.     vector<bool> visited(maxn, false);
  12.     visited[S] = true;
  13.    
  14.     int max_dist = 0;
  15.     int furthest_node = -1;
  16.     while(!q.empty()) {
  17.         int node = q.front();
  18.         q.pop();
  19.         int dist = q.front();
  20.         q.pop();
  21.        
  22.         if(max_dist < dist) {
  23.             max_dist = dist;
  24.             furthest_node = node;
  25.         }
  26.         for(int i = 0; i < (int) graph[node].size(); i++) {
  27.             int neighbour = graph[node][i];
  28.             if(!visited[neighbour]) {
  29.                 visited[neighbour] = true;
  30.                 q.push(neighbour);
  31.                 q.push(dist + 1);
  32.             }
  33.         }
  34.        
  35.     }
  36.     return make_pair(furthest_node, max_dist);
  37. }
  38. int main() {
  39.     int n;
  40.     cin >> n;
  41.     if(n == 1) {
  42.         cout << 0 << endl;
  43.         return 0;
  44.     }
  45.     for(int i = 1; i < n; i++) {
  46.         int a, b;
  47.         cin >> a >> b;
  48.         a--; b--;
  49.         graph[a].push_back(b);
  50.         graph[b].push_back(a);
  51.     }
  52.     int farthest_node_from_node_0 = bfs(0).first;
  53.     int res = bfs(farthest_node_from_node_0).second;
  54.    
  55.     cout << res << endl;
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement