Cod sursa(job #2772312)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 31 august 2021 18:25:21
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

std::ifstream fin ("darb.in");
std::ofstream fout ("darb.out");

int const nmax = 100005;
std::vector <int> adjacency[nmax];

// BFS
std::queue <int> q;
int dist[nmax];
int distmax, nodmax; // distanta maxima + nodul care se afla la ea

void BFS (int nodstart) {
    dist[nodstart] = 1;
    q.push(nodstart);
    while (!q.empty()) {
        int front = q.front();
        int contor = adjacency[front].size();
        for (int i = 0; i < contor; i++) {
            if (dist[adjacency[front][i]] == 0) {
                dist[adjacency[front][i]] = dist[front] + 1;
                if (distmax < dist[adjacency[front][i]]) {
                    distmax = dist[adjacency[front][i]];
                    nodmax = adjacency[front][i];
                }
                q.push(adjacency[front][i]);
            }
        }
        q.pop();
    }
}

int main() {
    int n;
    fin >> n;
    for (int i = n; i; i--) {
        int nod1, nod2;
        fin >> nod1 >> nod2;
        adjacency[nod1].push_back(nod2);
        adjacency[nod2].push_back(nod1);
    }
    distmax = 0;
    BFS (1);
    std::memset(dist, 0, sizeof(dist));
    distmax = 0;
    BFS (nodmax);
    fout << distmax;
    return 0;
}