Cod sursa(job #1706736)

Utilizator Cristi.96Ion Alexandru Cristian Cristi.96 Data 23 mai 2016 08:01:34
Problema Diametrul unui arbore Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define MAX 100000
ifstream f("darb.in");
ofstream g("darb.out");

vector <int> graf[MAX];
queue <int> coada;
int n, distanta[MAX], ver[MAX], last, diametru;

void bfs(int nod_start)
{
    memset(distanta, 0, MAX);
    memset(ver, 0, MAX);
    coada.push(nod_start);
    distanta[nod_start] = 1;
    ver[nod_start] = 1;
    int curent;
    while (!coada.empty())
    {
        curent = coada.front();
        for (int i = 0; i<graf[curent].size(); i++)
        {
            if (ver[graf[curent][i]] == 0)
            {
                coada.push(graf[curent][i]);
                distanta[graf[curent][i]] = distanta[curent] + 1;
                ver[graf[curent][i]] = 1;
                diametru = distanta[graf[curent][i]];
                last = graf[curent][i];
            }
        }
        coada.pop();
    }
}


int main()
{
    int x, y;
    f >> n;
    for (int i = 0; i < n - 1; i++)
    {
        f >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    bfs(1);
    bfs(last);
/*    cout << "diametru arborelui: " << diametru << endl;
    cout << "raza arborelui: " << diametru / 2 << endl;
    cout << "Centrul arborelui: ";
    for (int i = 1; i <= n; i++)
    {
        if (distanta[i] == diametru / 2)
            cout <<i<<" ";
    } */
    g << diametru;
    return 0;
}