Cod sursa(job #2960958)

Utilizator DKMKDMatei Filibiu DKMKD Data 5 ianuarie 2023 13:53:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N 1000001

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

vector<int> nod[MAX_N];
queue<int> coada;
int n, contor[MAX_N], viz[MAX_N], last, diametru;

void bfs(int plecare) {
    memset(contor, 0, MAX_N);
    memset(viz, 0, MAX_N);
    coada.push(plecare);
    contor[plecare] = 1;
    viz[plecare] = 1;
    int i, el;
    while (!coada.empty()) {
        el = coada.front();
        for (i = 0; i < nod[el].size(); i++) {
            if (viz[nod[el][i]] == 0) {
                coada.push(nod[el][i]);
                contor[nod[el][i]] = contor[el] + 1;
                viz[nod[el][i]] = 1;

                diametru = contor[nod[el][i]];
                last = nod[el][i];
            }
        }
        coada.pop();
    }
}

void citire() {
    int i, a, b;
    f >> n;
    for (i = 0; i < n - 1; i++) {
        f >> a >> b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
}

int main()
{
    citire();
    bfs(1);
    bfs(last);
    g << diametru;
    return 0;
}