Cod sursa(job #1171660)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 16 aprilie 2014 00:48:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#include <stdlib.h>

using namespace std;

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

vector< vector<int> > adj;
int N;
int *contor, *done;

int bfs(int nod){
	
	int elem, len;
	queue<int> q;
	q.push(nod);
	memset(done, 0, N*sizeof(int));
	done[nod] = 1;
	while(!q.empty()){
		elem = q.front();
		q.pop();
		len = adj[elem].size();
		for(int i = 0; i < len; i++){
			if(!done[adj[elem][i]]){
				done[adj[elem][i]] = 1;
				q.push(adj[elem][i]);
			}
		}
	}
	memset(contor, 0, N*sizeof(int));
	memset(done, 0, N*sizeof(int));
	q.push(elem);
	done[elem] = 1;
	while(!q.empty()){
		elem = q.front();
		q.pop();
		len = adj[elem].size();
		for(int i = 0; i < len; i++){
			if(!done[adj[elem][i]]){
				contor[adj[elem][i]] = contor[elem] + 1;
				q.push(adj[elem][i]);
				done[adj[elem][i]] = 1;
			}
		}
	}
	
	return contor[elem] + 1;
}

int main(){
	fin >> N;
	int a, b;
	vector<int> v;
	for(int i = 0; i < N; i++){
		adj.push_back(v);
	}
	contor = (int*)malloc(N*sizeof(int));
	done = (int*)malloc(N*sizeof(int));
	for(int i = 0; i < N-1; i++){
		fin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	fout << bfs(0);
	return 0;
}