Cod sursa(job #2469697)

Utilizator RedXtreme45Catalin RedXtreme45 Data 7 octombrie 2019 21:13:01
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
vector <int> v[100001];
vector <int>:: iterator it;
int c[100001];
int best,max1,max2;
void DFS(int x,int t)
{
    for (int i=1;i<=v[x][0];i++)
    {
        if (v[x][i]!=t)
        {
            DFS (v[x][i],x);
            if (c[i]+1>max1)
            {
                max2=max1;
                max1=c[i]+1;
            }
            else if (c[i]+1>max2)
            {
                max2=c[i]+1;
            }
        }
    }
    c[x]=max1+1;
    best=max(best,max1+max2+1);
}
int main()
{
    int a,b,i;
    fin>>n;
    for (i=1;i<=n;i++)
    {
        v[i].push_back(0);
    }
    for (i=1;i<n;i++)
    {
        fin>>a>>b;
        v[a][0]++;
        v[b][0]++;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    DFS (1,0);
    fout<<best-1;
    return 0;
}