Cod sursa(job #3124601)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 29 aprilie 2023 14:22:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 1e5;
int n;
int diametru;
vector<int> G[NMAX + 1];
int last;
bool viz[NMAX + 1], viz1[NMAX + 1];

void BFS(int start)
{
    viz[start] = 1;
    queue<int> Q;
    Q.push(start);
    while(!Q.empty())
    {
        int Node = Q.front();
        last = Node;
        Q.pop();

        for(int Vecin : G[Node])
            if(!viz[Vecin])
            {
                viz[Vecin] = 1;
                Q.push(Vecin);
            }
    }
}

void DFS(int k, int pasi)
{
    viz1[k] = 1;
    bool am_vecin = false;
    for(int Node : G[k])
        if(!viz1[Node])
        {
            am_vecin = true;
            DFS(Node, pasi + 1);
        }
    if(!am_vecin)
        diametru = max(diametru, pasi);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    BFS(1);
    DFS(last, 1);

    cout << diametru;


    return 0;
}