Cod sursa(job #1565629)

Utilizator BugirosRobert Bugiros Data 11 ianuarie 2016 08:08:12
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAXN = 100005;

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

int n;
vector<int> vecini[MAXN];

void citire()
{
    in >> n;
    int x,y;
    for (int i = 1;i < n;++i)
    {
        in >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
}

void dfs(int &ultim, int &diametru)
{
    bool vizitat[MAXN] = {0};
    int coada[MAXN] = {0};
    int dist[MAXN] = {0};
    int p = 1, q = 1;
    coada[1] = ultim;
    vizitat[ultim] = true;
    dist[ultim] = 1;
    diametru = 0;
    while (p <= q)
    {
        int nod = coada[p];
        coada[p++] = 0;
        for (unsigned int i = 0;i < vecini[nod].size();++i)
        {
            int vecin = vecini[nod][i];
            if (vizitat[vecin])
                continue;
            dist[vecin] = dist[nod] + 1;
            vizitat[vecin] = true;
            coada[++q] = vecin;
            if (dist[vecin] > diametru)
            {
                diametru = dist[vecin];
                ultim = vecin;
            }
        }
    }
}

int main()
{
    citire();
    int ultim, diametru;
    ultim = 1;
    dfs(ultim, diametru);
    dfs(ultim, diametru);
    out << diametru << '\n';
    return 0;
}