Cod sursa(job #2642807)

Utilizator JackstilAdascalitei Alexandru Jackstil Data 17 august 2020 12:29:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define nmax 100001

using namespace std;

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

vector <int> nod[nmax];
queue <int> coada;
int n, cnt[nmax], diametru, ultimul, x, y;
bool vizitat[nmax];

void bfs(int start) {
    coada.push(start);
    cnt[start] = 1;
    vizitat[start] = true;

    int v, j;
    while (!coada.empty()) {
        v = coada.front();

        for (int i = 0; i < (int)nod[v].size(); ++i) {
            j = nod[v][i];

            if (!vizitat[j]) {
                cnt[j] = cnt[v] + 1;
                vizitat[j] = true;
                coada.push(j);

                ultimul = j;
                diametru = cnt[j];
            }
        }

        coada.pop();
    }
}

int main() {
    in >> n;
    for (int i = 0; i < n - 1; ++i) {
        in >> x >> y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }

    bfs(1);

    memset(vizitat, false, sizeof(vizitat));
    memset(cnt, 0, sizeof(cnt));

    bfs(ultimul);

    out << diametru;
    return 0;
}