Cod sursa(job #2594535)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 6 aprilie 2020 12:12:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define N 100001
using namespace std;

int level[N];
vector <int> G[N];
int main () {
    ifstream fin ("darb.in");
    ofstream fout ("darb.out");

    int n, i, j, k, maxi=0;
    fin >> n;
    for (k=1; k<n; k++) {
        fin >> i >> j;
        G[i].push_back(j);
        G[j].push_back(i);
    }

    queue <int> Q;
    Q.push(1);
    level[1]=1;
    while (!Q.empty()) {
        auto save=Q.front();
        if (maxi<level[save]) {
            maxi=level[save];
            k=save;
        }
        Q.pop();

        for (auto it: G[save])
            if (!level[it]) {
                level[it]=level[save]+1;
                Q.push(it);
            }
    }

    memset(level, 0, sizeof level);
    Q.push(k);
    level[k]=1;
    while (!Q.empty()) {
        auto save=Q.front();
        if (maxi<level[save]) {
            maxi=level[save];
            k=save;
        }
        Q.pop();

        for (auto it: G[save])
            if (!level[it]) {
                level[it]=level[save]+1;
                Q.push(it);
            }
    }
    fout << maxi;
    return 0;
}