Cod sursa(job #1710994)

Utilizator RobertTanaseRobert Tanase RobertTanase Data 30 mai 2016 09:46:49
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
/* 2 parcurgeri BFS, incepand de la 1 respectiv de la ultimul termen din prima parcurgere
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAXN 1000001

using namespace std;

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

vector<int> graph[MAXN];
queue<int> q;
int n,contor[MAXN],visited[MAXN],last,diametru;


void bfs(int vertex) {
    memset(contor,0,MAXN);
    memset(visited,0,MAXN);

    q.push(vertex);
    contor[vertex] = 1;
    visited[vertex] = 1;

    int i,element;
    while(!q.empty()){
        element = q.front();
        for(i = 0; i < graph[element].size(); i++){
            if(visited[graph[element][i]] == 0){
                q.push(graph[element][i]);
                contor[graph[element][i]] = contor[element] + 1;
                visited[graph[element][i]] = 1;
                diametru = contor[graph[element][i]];
                last = graph[element][i];
            }
        }
        q.pop();
    }
}

void centru() {

}

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

int main()
{
    citire();
    bfs(1);
    //cout << "last = " << last;
    bfs(last);
    fout<<diametru;
    fin.close();
    fout.close();
    return 0;
}