Cod sursa(job #3233266)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 21:08:05
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>

using namespace std;

vector<int> adj[100001];
int dist[100001];

pair<int, int> bfs(int start, int n) {
    queue<int> q;
    q.push(start);
    memset(dist, -1, sizeof(dist));
    dist[start] = 0;

    int farthest_node = start;
    int max_dist = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
                if (dist[neighbor] > max_dist) {
                    max_dist = dist[neighbor];
                    farthest_node = neighbor;
                }
            }
        }
    }

    return {farthest_node, max_dist};
}

int main() {
    ifstream infile("darb.in");
    ofstream outfile("darb.out");

    int n;
    infile >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        infile >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Prima parcurgere BFS
    pair<int, int> first_bfs = bfs(1, n);
    // A doua parcurgere BFS
    pair<int, int> second_bfs = bfs(first_bfs.first, n);

    // Diametrul arborelui
    outfile << second_bfs.second << endl;

    infile.close();
    outfile.close();

    return 0;
}