Cod sursa(job #2048308)

Utilizator deleted_fb9d5fb04f7b88d9DELETED deleted_fb9d5fb04f7b88d9 Data 25 octombrie 2017 22:04:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NM 100001
using namespace std;

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

int  n;
vector <int> lista[NM];
int viz[NM], c[NM], p, u;

void bf (int x, int k);

int main() {
    int i;
    int x, y;

    fin >> n;
    for (i = 1; i < n; ++i) {
        fin >> x >> y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }

    bf (1, 1);
    bf (c[u], 1);

    fout << viz[ c[u] ] << '\n';

    return 0;
}

void bf (int x, int k) {
    int i;

    for (i = 1; i <= n; ++i) viz[i] = c[i] = 0;

    p = u = 0;
    c[p] = x;
    viz[x] = k;

    while (p <= u) {
        x = c[p];
        p++;
        for (i = 0; i < lista[x].size(); ++i)
            if (!viz[lista[x][i]]) {
                viz[lista[x][i]] = viz[x] + 1;
                u++;
                c[u] = lista[x][i];
            }
    }
}