Cod sursa(job #2701838)

Utilizator IuliaDamianDamian Iulia Alexandra IuliaDamian Data 1 februarie 2021 21:48:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

int n, x, y, finish_node, maxim;
vector <int> A[100005];
int dis[100005];
bool vizitat[100005];

void BFS(int start_node) {
    queue <int> coada;
    coada.push(start_node);
    vizitat[start_node] = true;
    while (!coada.empty()) {
        int nod = coada.front();
        coada.pop();
        for (int i = 0; i < A[nod].size(); ++i) {
            int vecin = A[nod][i];
            if (!vizitat[vecin]) {
                dis[vecin] = dis[nod] + 1;
                coada.push(vecin);
                vizitat[vecin] = true;
                finish_node = vecin;
                maxim = dis[vecin];
            }
        }
    }
}
int main() {
    fin >> n;
    for (int i = 1; i < n; ++i) {
        fin >> x >>  y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

    BFS(1);
    memset(dis, 0, sizeof(dis));
    memset(vizitat, false, sizeof(vizitat));

    BFS(finish_node);
    fout << maxim + 1;

}