Cod sursa(job #2902955)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 16 mai 2022 23:08:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

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

const int N = 1e5;
int viz[N + 1], l[N + 1];

vector <int> g[N + 1];

int n, a, b, nr, frunzacapat;

queue <int> q;

void bfs (int node, int val)
{
    q.push(node);
    viz[node] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (val == 1)
            frunzacapat = x;
        for (auto it : g[x])
            if (!viz[it])
            {
                q.push(it);
                viz[it] = 1;
                if (val == 2)
                    l[it] = l[x] + 1;
            }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1, 1);
    memset(viz, 0, sizeof(viz));
    bfs (frunzacapat, 2);
    int mx = -1;
    for (int i = 1; i <= n; ++i)
        mx = max (mx, l[i]);
    cout << mx + 1<< '\n';

    return 0;
}