Cod sursa(job #1095941)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 1 februarie 2014 11:51:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
using namespace std;
typedef struct celula {
            int nod;
            celula *next;
            } *lista;
lista arb[100005],v;
int i,x,y,n,jos[100005],tata[100005];
bool viz[100005];

void dfs1(int nod) {
     viz[nod]=1;
     int act=0;
     for (lista p=arb[nod]; p; p=p->next)
      if (viz[p->nod]==0)  { tata[p->nod]=nod; dfs1(p->nod); act=max(act,jos[p->nod]); } 
     jos[nod]=act+1;
}

int main(void) {
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin>>n;
    for (i=1; i<n; ++i) {
        fin>>x>>y;
        v=new celula; v->nod=x; v->next=arb[y]; arb[y]=v;
        v=new celula; v->nod=y; v->next=arb[x]; arb[x]=v;
        }
    dfs1(1);
    int sol=0;
    for (i=1; i<=n; ++i) {
        int s1=0,s2=0,f1;
        
        for (lista p=arb[i]; p; p=p->next) 
         if (p->nod!=tata[i]&&jos[p->nod]>s1) { s1=jos[p->nod]; f1=p->nod; }
         
        for (lista p=arb[i]; p; p=p->next)
         if (p->nod!=tata[i]&&jos[p->nod]>s2&&p->nod!=f1) s2=jos[p->nod];
        
        sol=max(sol,s1+s2+1);
        }
        
    fout<<sol;
 return(0);
}