Cod sursa(job #2534500)

Utilizator stormy_weatherelena cristina stormy_weather Data 30 ianuarie 2020 17:47:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

pair <int, int> bfs_from(int start, vector <vector <int>> &ch, int n) {
  //we remember the nodes we have seen
  vector <int> seen(n, 0);

  //we keep a queue with the node and the cur depth
  queue <pair <int, int>> bfs;
  bfs.push({start, 0});
  seen[start] = 1;

  pair <int, int> last_seen;
  while (!bfs.empty()) {
    last_seen = bfs.front();
    bfs.pop();
    int node = last_seen.first, depth = last_seen.second;
    for (int i = 0; i < (int) ch[node].size(); i++) {
      if (seen[ch[node][i]] == 0) {
        bfs.push({ch[node][i], depth + 1});
        seen[ch[node][i]] = 1;
      }
    }
  }

  return last_seen;
}

int main() {
  ifstream fin("darb.in");
  ofstream fout("darb.out");

  int n; fin >> n;
  vector <vector <int>> ch(n + 1, vector <int>());

  for (int i = 0; i < n; i++) {
    int a, b; fin >> a >> b;
    ch[a].push_back(b);
    ch[b].push_back(a);
  }

  int start = 1;
  while (ch[start].size() == 0)
    start++;

  pair <int, int> one_end = bfs_from(start, ch, n + 1);
  // cout << one_end.first << " " << one_end.second << "\n";

  pair <int, int> deep_end = bfs_from(one_end.first, ch, n + 1);
  // cout << deep_end.first << " " << deep_end.second << "\n";

  fout << deep_end.second + 1 << "\n";

  return 0;
}