Cod sursa(job #3216084)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 15 martie 2024 17:08:16
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> g[100005];

int dist1[100005], dist2[100005];

int bfs (int src, int dist[], int &best_nod)
{
    queue <int> q;
    int maxi=-1;
    q.push(src);
    dist[src]=0;
    while (!q.empty()) {
        int nod=q.front();
        q.pop();
        for (int vecin : g[nod]) {
            if (!dist[vecin]) {
                dist[vecin]=dist[nod]+1;
                q.push(vecin);
                maxi=max(maxi, dist[vecin]);
                best_nod=vecin;
            }
        }
    }
    return maxi;
}

int main()
{
    int n, x, y, best_nod;
    fin>>n;
    for (int i=1; i<=n-1; i++) {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int distan=bfs(1, dist1, best_nod);
    //cout<<distan<<" "<<best_nod<<endl;
    int diametru=bfs(best_nod, dist2, best_nod);
    //cout<<diametru<<" "<<best_nod<<endl;
    fout<<diametru+1;
    return 0;
}