Cod sursa(job #3288459)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 22 martie 2025 13:57:29
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f ("darb.in");
ofstream g ("darb.out");

const int NMAX = 100000;
int N, dMax, start;
bool viz[NMAX+1];

struct drum {
    int nod, dist;
};

vector<int> G[NMAX+1];
queue<drum> Q;

void citire() {
    f >> N;
    //
    int x, y;
    for (int i=1; i<N; i++) {
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void reset() {
    for (int i=1; i<=N; i++)
        viz[i] = 0;
}

void BFS(int nod) {
    Q.push({nod,1});
    while(!Q.empty()) {
        drum crt = Q.front();
        viz[crt.nod] = 1;
        Q.pop();
        //
        for (const auto &x : G[crt.nod])
            if (!viz[x])
                Q.push({x, crt.dist+1});
        //
        dMax = max(dMax, crt.dist);
        start = crt.nod;
    }
}

int main(){
    citire();
    //
    BFS(1);
    reset();
    BFS(start);
    //
    g << dMax;
    //
    f.close();
    g.close();
    return 0;
}