Cod sursa(job #1197396)

Utilizator DjokValeriu Motroi Djok Data 11 iunie 2014 20:30:29
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef struct lnod {
     int info;
     lnod *next;   
}*nod;

int i,n,x,y,s,rs,a[100005];
nod lda[100005];

void add(int x,nod &y)
{
  nod p=new lnod; 
  p->info=x;
  p->next=y;
  y=p;  
}

void dfs(int x)
{
  nod p=new lnod;
  for(p=lda[x];p;p=p->next)
  if(a[p->info]==0) {a[p->info]=a[x]+1; dfs(p->info);  }
}

int main()
{
  ifstream cin("darb.in");
  ofstream cout("darb.out");  
  
  cin>>n;
  
  for(i=1;i<n;i++)
  {
    cin>>x>>y;
    add(x,lda[y]);
    add(y,lda[x]);        
  }
  
  dfs(1); rs=0;
  for(i=1;i<=n;i++)
  if(a[i]>a[rs]) rs=i;
  
  memset(a,0,sizeof(a));
  dfs(rs); rs=0;
  for(i=1;i<=n;i++) 
  if(a[i]>a[rs]) rs=a[i];
    
  cout<<rs+1<<'\n';  
    
 return 0;   
}