Cod sursa(job #3191266)

Utilizator PetraPetra Hedesiu Petra Data 9 ianuarie 2024 10:23:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

#define NMAX 100002

using namespace std;

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

struct q_entry {
    int nod, index;
};

int n, x, y, val[NMAX], mx, nod_mx;
vector<int> G[NMAX];
queue<q_entry> q;

void bfs(int start)
{
    memset(val, 0, sizeof(val));

    q.push({start, 1});

    while (!q.empty())
    {
        q_entry c = q.front();
        q.pop();

        if (val[c.nod]) continue;
        val[c.nod] = c.index;
        mx = val[c.nod];
        nod_mx = c.nod;

        for (int i = 0; i < G[c.nod].size(); i++)
            q.push({G[c.nod][i], c.index + 1});
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs(1);
    bfs(nod_mx);

    fout << mx;
    return 0;
}