Cod sursa(job #1458784)

Utilizator ArambasaVlad Arambasa Arambasa Data 8 iulie 2015 14:05:41
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<vector>
using namespace std;
vector<int> vect[100005];
int dist[100005];
void dfs(int x)
{
   int i;
   for(i=vect[x].size()-1;i>=0;i--)
   if(dist[vect[x][i]]==0)
   {
       dist[vect[x][i]]=dist[x]+1;
       dfs(vect[x][i]);
   }
}
int main()
{
    ifstream in ("darb.in");
    ofstream out ("darb.out");
    int n,i,x,y,diam=0;
    in>>n;
    for(i=1;i<n;i++)
    {
        in>>x>>y;
        vect[x].push_back(y);
        vect[y].push_back(x);
    }
    dist[1]=1;
    dfs(1);
    for(i=1;i<=n;i++)
    {
    if(dist[i]>diam)
    {
        diam=dist[i];
        x=i;
    }
    dist[i]=0;
    }
    diam=0;
    dist[x]=1;
    dfs(x);
    for(i=1;i<=n;i++)
    if(dist[i]>diam)
    diam=dist[i];
    out<<diam;
    return 0;
}