Cod sursa(job #2695591)

Utilizator dianapingu1Diana Vasiliu dianapingu1 Data 13 ianuarie 2021 20:16:17
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX =  100001;

vector<int> graph[NMAX];
vector<int> dist;
int nod_start;
int diam;

void bfs(int nod) {

    fill(dist.begin(), dist.end(), 0);
    queue<int> q;

    dist[nod] = 1;
    q.push(nod);

    while(!q.empty()) {
        nod = q.front();
        q.pop();
        for(auto &vec : graph[nod]) {
            if(!dist[vec]) {
                dist[vec] = dist[nod] + 1;
                q.push(vec);
                nod_start = vec;
                diam = dist[vec];
            }
        }
    }
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");

    int n, x, y;
    fin >> n;
    dist.resize(n + 1);
    for(int i = 1; i <= n - 1; i++) {
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    bfs(1);
    bfs(nod_start);

    fout << diam << "\n";

    fin.close();
    fout.close();
    return 0;
}