Cod sursa(job #3312932)

Utilizator Tudor28Ceclan Tudor Tudor28 Data 30 septembrie 2025 20:33:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
#define NMAX 100005
vector<int> v[NMAX];
vector<int> t;
int cost[NMAX];
void bfs(int start)
{
    queue<int> q;
    q.push(start);
    cost[start] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        for (auto i : v[x])
        {
            if (cost[i])
                continue;

            cost[i] = cost[x] + 1;

            q.push(i);
        }
    }
}
int main()
{
    int n;
    fin >> n;
    int root;
    t.resize(n + 1);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        fin >> a >> b;
        t[b] = a;
        v[a].push_back(b);
        v[b].push_back(a);
        if (t[a] == 0)
        {
            root = a;
        }
    }

    bfs(root);
    int ind = 1;
    for (int i = 1; i <= n; i++)
    {

        if (cost[i] > cost[ind])
        {
            ind = i;
        }
    }
    memset(cost, 0, sizeof(cost));

    bfs(ind);
    for (int i = 1; i <= n; i++)
    {
        if (cost[i] > cost[ind])
        {
            ind = i;
        }
    }
    fout << cost[ind];
    return 0;
}