Cod sursa(job #1891935)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 24 februarie 2017 14:25:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 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];
int 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;
    }

    for(int i = 1; i <= n; 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;
}