Cod sursa(job #2924179)

Utilizator Teodor11Posea Teodor Teodor11 Data 26 septembrie 2022 18:53:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

deque<int> q;
vector<int> neighbors[100000];
int n, x, y, visited[100000], counter[100000], last_visited_node, diameter;

void bfs(int starting_node) {
    q.push_back(starting_node);
    visited[starting_node] = 1;
    counter[starting_node] = 1;
    while (!q.empty()) {
        /*
        cout << "Current Node: " << q.front() + 1;
        cout << "\nIts neighbors: ";
        for (int i = 0; i < neighbors[q.front()].size(); ++i) {
            cout << neighbors[q.front()][i] + 1 << ' ';
        }
        cout << "\nCurrent Queue: ";
        for (int i = 0; i < q.size(); ++i) {
            cout << q[i] + 1 << ' ';
        }
        */
        int current_size = neighbors[q.front()].size();
        for (int i = 0; i < current_size; ++i) {
            if (!visited[neighbors[q.front()][i]]) {
                q.push_back(neighbors[q.front()][i]);
                visited[neighbors[q.front()][i]] = 1;
                counter[neighbors[q.front()][i]] = counter[q.front()] + 1;
            }
            diameter = counter[q.front()];
            last_visited_node = q.front();
        }
        q.pop_front();
        /*
        cout << "\nNew Queue: ";
        for (int i = 0; i < q.size(); ++i) {
            cout << q[i] + 1 << ' ';
        }
        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) {
        fin >> x >> y;
        neighbors[x - 1].push_back(y - 1);
        neighbors[y - 1].push_back(x - 1);
    }
    bfs(0);
    reset();
    bfs(last_visited_node);
    fout << diameter;
    return 0;
}