Cod sursa(job #2162556)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 12 martie 2018 11:52:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
//diametrul unui arbore
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

const int N=1e5+4;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector<int> G[N];
bool viz[N];
int n,d[N],dmax;

inline void read()
{
    int x,y,i;
    fin>>n;
    for(i=1;i<=n;i++)
    {
         fin>>x>>y;
         G[x].push_back(y);
         G[y].push_back(x);
    }
}

void dfs(int x)
{
    viz[x]=1;
    for(std::vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
    {
        if(!viz[*it])
        {
            d[(*it)]=d[x]+1;
            dfs(*it);
        }
    }
}


void solve()
{
    int ret,i;
    d[3]=1;
    dfs(3);
    dmax=-1;
    for(i=1;i<=n;i++)
    {
        if(d[i]>dmax)
        {
            dmax=d[i];
            ret=i;
        }
        viz[i]=0;
        d[i]=0;
    }

    //cout<<ret;

    d[ret]=1;
    dfs(ret);

    dmax=-1;
    for(i=1;i<=n;i++)
        if(d[i]>dmax)
    {
        dmax=d[i];
    }

    fout<<dmax;

}


int main()
{
    read();
    solve();
}