Cod sursa(job #2510467)

Utilizator Vladymyr11Pechi Vladimir Stefan Vladymyr11 Data 16 decembrie 2019 19:29:52
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
using namespace std;
vector <int> v[100001];
int dist1[100001],dist2[100001],c[100001];
int main()
{
    ifstream fin ("dfs.in");
    ofstream fout ("dfs.out");
    int n,m,x,y,s,p=1,u=1;
    fin>>n;
    for (int i=1;i<n;i++)
        {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        }
    c[u]=1;
    dist1[1]=1;
    while (p<=u)
        {
        int vf=c[p];
        p++;
        int l=v[vf].size();
        for (int i=0;i<l;i++)
            {
            if (dist1[v[vf][i]]==0)
                {
                u++;
                c[u]=v[vf][i];
                dist1[v[vf][i]]=dist1[vf]+1;
                }
            }
        }
    int imax=1;
    int maxim=dist1[1];
    for (int i=2;i<=n;i++)
        if (dist1[i]>maxim)
            {
            maxim=dist1[i];
            imax=i;
            }
     u=p=1;
    c[u]=imax;
    dist2[imax]=1;
    while (p<=u)
        {
        int vf=c[p];
        p++;
        int l=v[vf].size();
        for (int i=0;i<l;i++)
            {
            if (dist2[v[vf][i]]==0)
                {
                u++;
                c[u]=v[vf][i];
                dist2[v[vf][i]]=dist2[vf]+1;
                }
            }
        }
    maxim=dist2[1];
    for (int i=2;i<=n;i++)
        if (dist2[i]>maxim)
            maxim=dist2[i];
    fout<<maxim;
    return 0;
}