Cod sursa(job #2389632)

Utilizator EricEric Vilcu Eric Data 27 martie 2019 12:24:15
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
vector<int>a[100001];
bool v[100001];
int n,x,y;
int bfs()
{
    int b=0,e=1,l[100001];
    l[0]=1;v[1]=1;
    while(b<e)
    {
        int c=l[b],m=a[l[b]].size();
        for(int i=0;i<m;++i)if(!v[a[c][i]]){v[a[c][i]]=1;l[e]=a[c][i];++e;};
        ++b;
    }
    return l[b-1];
}
int dfs(int x,int d)
{
    int c=x,m=a[x].size();
    for(int i=0;i<m;++i)if(!v[a[c][i]]){v[a[c][i]]=1;d=max(d,dfs(a[c][i],d+1));}
    return d;
}
int main()
{
    f>>n;
    for(int i=1;i<n;++i){f>>x>>y;a[x].push_back(y);a[y].push_back(x);}
    x=bfs();
    for(int i=1;i<=n;++i)v[i]=0;
    g<<dfs(x,0);
}