Cod sursa(job #3295739)

Utilizator miruna_iliescuIliescu Miruna miruna_iliescu Data 8 mai 2025 09:08:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1 << 30

void read_input(int& n, vector<vector<int>>& adj) {
    ifstream fin("darb.in");
    fin >> n;
    adj.resize(n + 1);

    int x, y;
    // Arborele este un graf neorientat
    for (int i = 0; i < n - 1; i++) {
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    fin.close();
}

// BFS care porneste dintr-un nod dat si returneaza o pereche cu:
// cel mai indepartat nod in care poate ajunge si distanta pana la acesta
pair <int, int> bfs_farthest(int node, int n, vector<vector<int>>& adj) {
    vector<int> dist(n + 1, INF);
    queue<int> q;

    dist[node] = 0;
    q.push(node);

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

        for (int neigh : adj[node]) {
            if (dist[neigh] == INF) {
                dist[neigh] = dist[node] + 1;
                q.push(neigh);
            }
        }
    }

    int far_node = node;
    int max_dist = 0;
    for (int u = 1; u <= n; u++) {
        if (dist[u] > max_dist) {
            max_dist = dist[u];
            far_node = u;
        }
    }

    return {far_node, max_dist};
}

void print_output(const int& diam) {

    ofstream fout ("darb.out");
    fout << diam << endl;
    fout.close();

}

int main() {
    int n;
    vector<vector<int>> adj;
    read_input(n, adj);

    // 1) pornesc un BFS dintr-un nod oarecare (1)
    pair <int, int> p1 = bfs_farthest(1, n, adj);
    int farthest_node = p1.first;

    // 2) pornesc un DFS din nodul gasit, pentru a obtine diametru
    pair<int, int> p2 = bfs_farthest(farthest_node, n, adj);
    int diametru_in_nodes = p2.second + 1;

    print_output(diametru_in_nodes);
    
    return 0;
}