Cod sursa(job #1891925)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 24 februarie 2017 14:15:56
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<iostream>
#include<vector>
#define RTP 0

using namespace std;

const int MAXN = 100005;

ifstream re ("darb.in");
ofstream we ("darb.out");

vector <int> rb[MAXN];
int tata[MAXN], lung[MAXN], viz[MAXN];
int n;


void findingtati(int nod)
{
    for(auto &it : rb[nod])
    {
        if(!tata[it])
        {
            tata[it] = nod;
            findingtati(it);
        }
    }
}


void calclant(int nod)
{
    //viz[nod] = 1;
    for(auto &it : rb[nod])
    {
        if(lung[it] == 0)
        {
            lung[it] = lung[nod] + 1;
            calclant(it);
        }
    }
}

int main ()
{
    re >> n;
    for(int i = 1; i < n; i++)
    {
        int a, b;
        re >> a >> b;
        rb[a].push_back(b);
        rb[b].push_back(a);
    }

    tata[1] = -1;

    findingtati(1);

    if(RTP)
        for(int i = 1; i <= n; i++)
        {
            cout << tata[i] << ' ';
        }

    lung[1] = 1;
    calclant(1);

    if(RTP)
    {
        cout << endl;
        for(int i = 1; i <= n; i++)
        {
            cout << lung[i] << ' ';
        }
    }

    int maxx = 1;

    for(int i = 1; i <= n; i++)
    {
        if(lung[i] > lung[maxx])
        {
            maxx = i;
        }
        lung[i] = 0;
    }
    lung[maxx] = 1;


    calclant(maxx);

    if(RTP)
    {
        cout << endl;
        for(int i = 1; i <= n; i++)
        {
            cout << lung[i] << ' ';
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(lung[i] > lung[maxx])
        {
            maxx = i;
        }
    }

    we << lung[maxx];


    re.close();
    we.close();

    return 0;
}