Cod sursa(job #2960574)

Utilizator Teodor11Posea Teodor Teodor11 Data 4 ianuarie 2023 18:07:22
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

const int MAX_SIZE = 100001;
deque<int> nodes;
vector<int> neighbors[MAX_SIZE];
int n, visited[MAX_SIZE], level[MAX_SIZE], last_visited_node, diameter;

void bfs(int starting_node) {
    nodes.push_back(starting_node);
    visited[starting_node] = 1;
    level[starting_node] = 1;
    while (!nodes.empty()) {
        /*
        cout << "Current Node: " << nodes.front();
        cout << "\nIts neighbors: ";
        for (int i = 0; i < neighbors[nodes.front()].size(); ++i) {
            cout << neighbors[nodes.front()][i] << ' ';
        }
        cout << "\nCurrent Queue: ";
        for (int i = 0; i < nodes.size(); ++i) {
            cout << nodes[i] << ' ';
        }
        */
        int curr_node = nodes.front();
        int curr_neighbors_num = neighbors[curr_node].size();
        nodes.pop_front();
        for (int i = 0; i < curr_neighbors_num; ++i) {
            if (!visited[neighbors[curr_node][i]]) {
                nodes.push_back(neighbors[curr_node][i]);
                visited[neighbors[curr_node][i]] = 1;
                level[neighbors[curr_node][i]] = level[curr_node] + 1;
            }
            diameter = level[curr_node];
            last_visited_node = curr_node;
        }
        /*
        cout << "\nNew Queue: ";
        for (int i = 0; i < nodes.size(); ++i) {
            cout << nodes[i] << ' ';
        }
        cout << "\nlast: " << last_visited_node + 1;
        cout << "\ndiameter: " << diameter << "\n\n";
        */
    }
}

void reset() {
    for (int i = 0; i < n; ++i) {
        visited[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';
    }
    */
    bfs(1);
    reset();
    bfs(last_visited_node);
    fout << diameter;
    return 0;
}