Cod sursa(job #1881515)

Utilizator gabib97Gabriel Boroghina gabib97 Data 16 februarie 2017 16:02:29
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <vector>
#define N 100005
using namespace std;

int n,diam,h[N];
vector<int> G[N];

void DFS(int s)
{
    int i,z=G[s].size(),m1,m2;
    m1=m2=0;
    h[s]=1;
    for (i=0;i<z;i++)
        if (!h[G[s][i]])
        {
            DFS(G[s][i]);
            h[s]=max(h[s],h[G[s][i]]+1); //max depth
            if (h[G[s][i]]>m1) m2=m1,m1=h[G[s][i]];
            else if (h[G[s][i]]>m2) m2=h[G[s][i]];
        }
    if (m2) diam=max(diam,m1+m2+1);
    else diam=max(diam,m1);
}

int main()
{
    freopen ("darb.in","r",stdin);
    freopen ("darb.out","w",stdout);
    scanf("%i",&n);
    int i,x,y;
    for (i=1;i<n;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1);
    printf("%i",diam);
    fclose(stdin);
    fclose(stdout);
    return 0;
}