Cod sursa(job #2237633)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 2 septembrie 2018 14:44:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 100001;

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

vector<int> A[NMAX];
queue<int> C;
int d[NMAX],
    lMax, lst, n;

void bfs(int x) {
    C.push(x);
    d[x] = 1;
    int crt = 0;
    while(!C.empty()) {
        crt = C.front();
        C.pop();
        for(auto i: A[crt])
            if(d[i] == 0) {
                d[i] = d[crt]+1;
                lst = i;
                lMax = d[i];
                C.push(i);
            }
    }
    for(int i = 1; i <= n; i++)
        d[i] = 0;
}

int main()
{
    int x, y;
    in >> n;

    while(in >> x >> y) {
        A[x].push_back(y);
        A[y].push_back(x);
    }

    bfs(1);
    bfs(lst);

    out << lMax;
    return 0;
}