Cod sursa(job #1293941)

Utilizator anarogozAna Rogoz anarogoz Data 16 decembrie 2014 19:54:32
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX = 100000;
vector <int> v[NMAX + 2];
int h[NMAX + 2], pred[NMAX + 2], sol[NMAX + 2];
bool viz[NMAX + 2];
void dfs(int k)
{
    int i;
    viz[k] = true;
    for(i = 0; i < v[k].size(); i++)
        if(!viz[v[k][i]])
        {
            pred[v[k][i]] = k;
            dfs(v[k][i]);
        }
    if(h[k] + 1 > h[pred[k]])
        h[pred[k]] = h[k] + 1;
}
int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int n, i, x, y;
    scanf("%d", &n);
    for(i = 1; i < n; i++)
    {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i = 1; i <= n; i++)
        if(v[i].size() == 1)
            h[i] = 1;
    dfs(1);
    int max1 = 0, ind1;
    for(i = 0; i < v[1].size(); i++)
        if(h[v[1][i]] > max1)
        {
            max1 = h[v[1][i]];
            ind1 = v[1][i];
        }
    int max2 = 0, ind2;
    for(i = 0; i < v[1].size(); i++)
        if(h[v[1][i]] > max2 && (h[v[1][i]] < max1 || (h[v[1][i]] == max1 && v[1][i] != ind1)))
        {
            max2 = h[v[1][i]];
            ind2 = v[1][i];
        }
    printf("%d\n", max1 + max2 + 1);
   /* int poz = max1 - 1;
    sol[max1 + 1] = 1;
    sol[max1] = ind1;
    int hc = h[ind1];
    sol[0] = max1 + 1;
    while(hc > 1)
    {
        for(i = 0; i < v[ind1].size(); i++)
            if(h[v[ind1][i]] == hc - 1)
            {
                sol[poz] = v[ind1][i];
                poz --;
                ind1 = v[ind1][i];
                hc --;
                break;
            }
    }

    hc = h[ind2];
    sol[++sol[0]] = ind2;
    while(hc > 1)
    {
        for(i = 0; i < v[ind2].size(); i++)
            if(h[v[ind2][i]] == hc - 1)
            {
                sol[++sol[0]] = v[ind2][i];
                ind2 = v[ind2][i];
                hc --;
                break;
            }
    }
    for(i = 1; i <= sol[0]; i ++)
        printf("%d ", sol[i]);
    printf("\n");*/
    return 0;
}