Cod sursa(job #2695365)

Utilizator Andrei1Mariciuc Andrei-Alexandru Andrei1 Data 12 ianuarie 2021 17:18:59
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> edges;
vector<bool> used;
vector<int> d;
int lastNode;

void dfs(int u) {
  d[u] = 0;
  used[u] = true;
  queue<int> q;
  q.push(u);

  while(!q.empty()) {
    u = q.front();
    q.pop();
    for(int v: edges[u])
      if(!used[v]) {
        used[v] = true;
        d[v] = d[u] + 1;
        lastNode = v;
        q.push(v);
      }
  }
}


int main() {
  freopen("darb.in", "r", stdin);
  freopen("darb.out", "w", stdout);
  int n;
  cin >> n;
  edges.resize(n);
  used.resize(n);
  d.resize(n);
  for(int i=0; i<n-1; i++) {
    int u, v;
    cin >> u >> v;
    edges[u - 1].push_back(v - 1);
    edges[v - 1].push_back(u - 1);
  }

  int random = 0;
  dfs(random);
  int node1 = lastNode;
  used.assign(n, 0);
  d.assign(n, 0);
  int d1 = d[node1];
  dfs(node1);
  int node2 = lastNode;
  cout << d[lastNode] + d1 + 1;

  return 0;
}