Cod sursa(job #2846623)

Utilizator PechiPecherle George Pechi Data 9 februarie 2022 13:54:49
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
/*
   darb.cpp
   By: Pecherle George Daniel (Pechi)
   Created: 09/02/2022 12:35:54 by Pechi
   Updated: 09/02/2022 13:53:34 by Pechi
*/
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
ifstream fin("darb.in");
ofstream fout("darb.out");

int n,ultimul,diametru;
vector<vector<int>> adj;
bitset<100001> vizitat;

void citire()
{
  int x,y;
  fin>>n;
  adj.resize(n+1);
  while(fin>>x>>y){
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
}

void bfs(int start)
{
  int niv;
  queue<pii> coada;
  coada.push({start,0});

  while(!coada.empty())
  {
    pii el = coada.front();
    coada.pop();

    vizitat[el.first] = true;
    ultimul = el.first;
    niv = el.second;

    if(niv>diametru)
      diametru = niv;

    for(auto vecin:adj[el.first])
      if(!vizitat[vecin])
        coada.push({vecin,++niv});
  }
}

int main()
{
  citire();
  bfs(1);
  vizitat.reset();
  bfs(ultimul);
  fout<<diametru;
  return 0;
}