Cod sursa(job #2708854)

Utilizator elena_dElena Dulgheru elena_d Data 19 februarie 2021 15:24:59
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("probl.in");
ofstream cout("probl.out");
int coada[100001], viz[100001], n, k, d[100001];
vector<int>a[100001];
void bfs(int nod)
{
    int inc = 1, sf = 1;
    coada[inc] = nod;
    viz[nod] = 1;
    d[nod] = 1;
    while (inc <= sf)
    {
        for (int i = 0; i < a[coada[inc]].size(); i++)
        {
            if (viz[a[coada[inc]][i]] == 0)
            {
                coada[++sf] = a[coada[inc]][i];
                viz[a[coada[inc]][i]] = 1;
                d[a[coada[inc]][i]] = d[coada[inc]] + 1;
            }
        }
        inc++;
    }
}
int main()
{
    int i, j, s = 0;
    cin >> n;
    while (cin >> i >> j)
    {
        
        a[i][j] = a[j][i] = 1;
    }
    bfs(1);
    int maxi = 0, nod = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] > maxi)
            maxi = d[i], nod = i;
    for (i = 1; i <= n; i++)
    {
        viz[i] = 0;
        d[i] = 0;
    }
    bfs(nod);
    maxi = 0;

    for (int i = 1; i <= n; i++)
        if (d[i] > maxi)
            maxi = d[i];
    cout << maxi;
    return 0;
}