Cod sursa(job #2355213)

Utilizator crion1999Anitei cristi crion1999 Data 25 februarie 2019 21:38:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 100005
using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");

int N;
vector<int> graph[NMAX];
int dist[NMAX];
queue<int> q;

void BFS(int i)
{
    for(int i = 1; i <= N; ++i)
        dist[i] = 0x3f3f3f3f;
    dist[i] = 1;
    q.push(i);

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(auto y : graph[nod])
        {
            if(dist[y] > dist[nod] + 1)
            {
                dist[y] = dist[nod] + 1;
                q.push(y);
            }
        }
    }
}

int main()
{
    fi >> N;
    for(int i = 1; i <= N-1; ++i)
    {
        int a,b;
        fi >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    BFS(1);
    int maxx = 0;
    int node;
    for(int i = 1; i <= N; ++i)
    {
        if(maxx < dist[i])
        {
            maxx = dist[i];
            node = i;
        }
    }
    maxx = 0;
    BFS(node);
    for(int i = 1; i <= N; ++i)
    {
        if(maxx < dist[i])
        {
            maxx = dist[i];
            node = i;
        }
    }
    fo << maxx;
}