Pagini recente » Borderou de evaluare (job #1244892) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2932602) | Cod sursa (job #1710994)
/* 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;
}