Cod sursa(job #2961526)

Utilizator Teodor11Posea Teodor Teodor11 Data 6 ianuarie 2023 17:04:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_SIZE = 100000;
vector<int> neighbors[MAX_SIZE + 1];
int n, level[MAX_SIZE + 1], last_visited_node, diameter;

void graph_traversal(int node) {
    if (!level[node]) {
        ++level[node];
    }
    if (diameter < level[node]) {
        diameter = level[node];
        last_visited_node = node;
    }
    int node_neighbors = neighbors[node].size();
    for (int i = 0; i < node_neighbors; ++i) {
        int act_neighbor = neighbors[node][i];
        if (!level[act_neighbor]) {
            level[act_neighbor] = level[node] + 1;
            graph_traversal(act_neighbor);
        }
    }
}

void reset_node_level() {
    for (int i = 1; i <= n; ++i) {
        level[i] = 0;
    }
}

int main() {
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        fin >> x >> y;
        neighbors[x].push_back(y);
        neighbors[y].push_back(x);
    }
    /*
    for (int i = 1; i <= n; ++i) {
        cout << "Neighbors of node " << i << " are: ";
        for (int j = 0; j < neighbors[i].size(); ++j) {
            cout << neighbors[i][j] << ' ';
        }
        cout << '\n';
    }
    */
    graph_traversal(1);
    reset_node_level();
    graph_traversal(last_visited_node);
    fout << diameter;
    return 0;
}