Cod sursa(job #2909022)

Utilizator dgivanDan Grigore Ivan dgivan Data 7 iunie 2022 22:31:55
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include<iostream>
#include<set>
#include<algorithm>
#include <vector>
#include <fstream>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>

using namespace std;

int n;
vector<int> v[110000];
vector<int> viz(110000);

int main () {
    ifstream cin ("darb.in");
    ofstream cout ("darb.out");
    
    cin >> n;
    for (int i = 1; i<=n-1; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    queue<int> q;
    q.push(1);
    viz[1] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i<v[u].size();i++){
            if (!viz[v[u][i]]){
                q.push(v[u][i]);
                viz[v[u][i]] = viz[u]+1;
            }
        }
    }
    int max = 0;
    int frunza;
    for (int i = 1; i<=n; i++){
        if (viz[i] > max){
            max = viz[i];
            frunza = i;
        }
    }

    for (int i = 1; i<=n; i++){
        viz[i] = 0;
    }

    q.push(frunza);
    viz[frunza] = 1;
    while (!q.empty()){
        int w = q.front();
        q.pop();
        for (int i = 0; i<v[w].size(); i++){
            if (!viz[v[w][i]]){
                q.push(v[w][i]);
                viz[v[w][i]] = viz[w]+1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i<=n; i++){
        if (viz[i]>ans){
            ans = viz[i];
        }
    }
    cout << ans;
}