Cod sursa(job #2392603)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 30 martie 2019 11:01:34
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

const int NMAX = 100000;

int N;
int dist[NMAX + 5];
vector <int> g[NMAX + 5];
queue <int> q;

void BFS(int node)
{
    q.push(node);
    dist[node] = 1;

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

        for(auto it : g[currentNode])
            if(!dist[it])
            {
                dist[it] = dist[currentNode] + 1;
                q.push(it);
            }
    }
}

int main()
{
    fin >> N;

    int x, y;
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    BFS(1);

    int maxDist = 0, maxDistNode = -1;

    for(int i = 1; i <= N; i++)
        if(dist[i] > maxDist)
        {
            maxDist = dist[i];
            maxDistNode = i;
        }

    memset(dist, 0, sizeof(dist));

    BFS(maxDistNode);

    maxDist = 0;

    for(int i = 1; i <= N; i++)
        maxDist = max(maxDist, dist[i]);

    fout << maxDist << '\n';

    return 0;
}