Cod sursa(job #2814046)

Utilizator oporanu.alexAlex Oporanu oporanu.alex Data 7 decembrie 2021 14:51:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
const int nmax = 100005;
vector<int> adj[nmax];
int dist[nmax] = {-1};
int last;
void bfs(int src){
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    while(!q.empty())
    {
        int tata = q.front();
        q.pop();

        for(auto copil : adj[tata])
        {
            if(dist[copil] == -1)
                {
                    dist[copil] = dist[tata] + 1;
                    q.push(copil);
                    last = copil;
                }
        }
    }
}
int main()
{
    for(int i = 1; i <= nmax; ++i)
        dist[i] = -1;
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    int V, E;
    fin >> V;
    for(int i = 0; i < V - 1; ++i){
        int src, dst;
        fin >> src >> dst;
        adj[src].push_back(dst);
        adj[dst].push_back(src);
    }
    bfs(1);
    for(int i = 1; i <= nmax; ++i)
        dist[i] = -1;
    int x = last;

    bfs(x);

    fout << dist[last] + dist[x] + 1<< '\n';
    return 0;
}