Cod sursa(job #2985237)

Utilizator samyro14Samy Dragos samyro14 Data 25 februarie 2023 23:21:49
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

#define ll unsigned long long
#define fast_read ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

const int maxn = 1e5;
const int mod = 1e6 + 7;
//
int n;
int t[maxn + 2];
int b[maxn + 2];
int root, plec, max1;
vector<int> a[maxn + 2];
bitset<maxn + 2> visited;

void init(){
  for(int i = 1; i <= n; ++i)
    t[i] = i;
}
void read(){
  for(int i = 1; i < n; ++i){
      int x, y;
      fin >> x >> y;
      t[y] = x;
      a[x].push_back(y);
      a[y].push_back(x);
  }
}
int get_root(){
  for(int i = 1; i <= n; ++i)
    if(t[i] == i)
      return i;
  return 0;
}

void bfs(int start){
  queue<int> q;
  q.push(start);
  b[start] = 1;
  visited[start] = 1;
  while(!q.empty()){
    int i = q.front();
    for(auto x : a[i]){
      if(!visited[x]){
        visited[x] = 1;
        q.push(x);
        b[x] = b[i] + 1;
      }
    }
    q.pop();
  }
}
int main(){
  fin >> n;
  init();
  read();
  //plec din root
  root = get_root();
  bfs(root); // ma voi duce la cel mai jos nivel posibil
  for(int i = 1; i <= n; ++i)
    if(b[i] > max1) max1 = b[i], plec = i; 
  for(int i = 1; i <= n; ++i)
    b[i] = 0, visited[i] = 0;
  bfs(plec);
 
  max1 = 0;
  for(int i = 1; i <= n; ++i)
    max1 = max(max1, b[i]);
  fout << max1;
  
  return 0;
}
/*

*/