Cod sursa(job #2713839)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 28 februarie 2021 18:53:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

const int NMAX = 100001;

int n, last;
vector<int>G[NMAX];
int dist[NMAX];

void citire()
{
    f >> n;
    int x, y;
    while(f >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void BFS(int nod)
{
    dist[nod]=1;
    bool viz[NMAX] = {0};
    int Q[NMAX];
    int p, u;
    p = u = 1;
    viz[nod] = 1;
    Q[p] = nod;
    while(p <= u)
    {
        for(auto &x : G[Q[p]])
            if(viz[x] == 0)
            {
                Q[++u] = x;
                viz[x] = 1;
                dist[x]=dist[Q[p]]+1;
            }
        p++;
    }
    last = Q[u];
}

int main()
{
    citire();
    BFS(1);
    BFS(last);
    g<<dist[last];
    return 0;
}