Cod sursa(job #2420356)

Utilizator CameliaSSamoilescu Camelia CameliaS Data 11 mai 2019 16:34:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define NMAX 100005

vector<int> graph[NMAX];
queue<int> coada;
int viz[NMAX], lungime[NMAX];
int n, ultim;


void citire(){
    f>>n;
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        f>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void bfs(int sursa){

    for(int i = 1; i <= n; i ++)
        {
        viz[i] = 0;
        lungime[i] = 0;
        }

    viz[sursa] = 1;
    coada.push(sursa);
    while(!coada.empty()){
       int nod = coada.front();
        coada.pop();

        for(int i = 0; i < graph[nod].size(); i ++)
        {
            int vecin = graph[nod][i];
            if(!viz[vecin])
                {
                    viz[vecin] = 1;
                    lungime[vecin] = lungime[nod]+1;
                    coada.push(vecin);
                }
        }
        if(coada.empty())
            ultim = nod;

    }

}


int main()
{
    citire();
    bfs(1);
    bfs(ultim);
    int max = lungime[1];
    for(int i = 2; i <= n; i ++){
        if(lungime[i] > max)
            max = lungime[i];}
    g<< max + 1;
    return 0;
}