Cod sursa(job #3141176)

Utilizator DumitrescuADumitrescuA DumitrescuA Data 13 iulie 2023 10:47:35
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream cin("darb.in");
ofstream cout("darb.out");

vector <int> v[100001];
int dist[100001];
bool fost[100001];

void bfs(int x){
    int poz,i;
    queue<int> mers;
    mers.push(x);
    fost[x]=1;dist[x]=0;
    while(!mers.empty()){
        poz=mers.front();
        mers.pop();
        for(i=0;i<v[poz].size();i++){
            if(fost[v[poz][i]]==0){
                dist[v[poz][i]]=dist[poz]+1;
                fost[v[poz][i]]=1;
                mers.push(v[poz][i]);
            }
        }
    }
}

void curat(){
    int i;
    for(i=0;i<=100000;i++)
        fost[i]=dist[i]=0;
}

int main()
{
    int n,max1,ci,i,a,b;
    cin>>n;
    for(i=0;i<n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(1);
    max1=ci=-1;
    for(i=1;i<=n;i++){
        //printf("%d %d\n",i,dist[i]);
        if(dist[i]>max1){
            max1=dist[i];
            ci=i;
        }
    }
    //printf("%d ",ci);
    curat();
    bfs(ci);
    max1=-1;
    for(i=1;i<=n;i++){
        max1=max(max1,dist[i]);
    }
    cout<<max1;
    return 0;
}