Cod sursa(job #2460130)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 22 septembrie 2019 20:17:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int MAXN = 1e5 + 5;

using namespace std;

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

queue<int>coada;
vector<int>graf[MAXN];
bool viz[MAXN];
int n,dp[MAXN];

pair<int,int> bfs(int nod){
    for(int i = 1; i <= n; i++){
        dp[i] = 0;
        viz[i] = false;
    }
    coada.push(nod);

    while(coada.size()){
        int nod = coada.front();
        coada.pop();

        for(int i = 0; i < graf[nod].size(); i++){
            int curent = graf[nod][i];
            if(!viz[curent]){
                viz[curent] = true;
                dp[curent] = dp[nod] + 1;
                coada.push(curent);
            }
        }
    }
    int maxim = 0,nod_maxim;
    for(int i = 1; i <= n; i++){
        if(dp[i] > maxim){
            maxim = dp[i];
            nod_maxim = i;
        }
    }
    return {nod_maxim,maxim + 1};
}

int main()
{
    in>>n;
    for(int i = 1; i <= n; i++){
        int nod1,nod2;
        in>>nod1>>nod2;
        graf[nod1].push_back(nod2);
        graf[nod2].push_back(nod1);
    }
    int nod_maxim = bfs(1).first;
    int diametru = bfs(nod_maxim).second;
    out<<diametru;
    return 0;
}