Cod sursa(job #1476240)

Utilizator alexandru.huleaAlexandru Hulea alexandru.hulea Data 24 august 2015 18:36:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;

typedef struct nod {
	int index;
	int distanta;
} nod;

// pornind de la sursa prin vectorii de vecini rulez bfs
nod* bfs(vector<nod*>* vecini, nod* sursa, int* maxDistance) {
	bool* visited = new bool[n];
	for (int i = 0; i < n; i++) {
		visited[i] = false;
	}
	nod* last = sursa;
	queue<nod*> q;
	q.push(sursa);
	visited[sursa->index] = true;
	while(!q.empty()) {
		nod* current = q.front();
		q.pop();
		for (int j = 0; j < vecini[current->index].size(); j++) {
			nod* vecin = vecini[current->index][j];
			if (!visited[vecin->index]) {
				vecin->distanta = current->distanta + 1;
				q.push(vecin);
				visited[vecin->index] = true;
				if (*maxDistance < vecin->distanta) {
					*maxDistance = vecin->distanta;
					last = vecin;
				}
			}
		}
	}
	return last;
}

int main() {
	
	freopen("darb.in", "r", stdin);
	freopen ("darb.out","w",stdout);
	
	scanf("%i", &n);
	vector<nod*>* vecini = new vector<nod*>[n]; 
	nod* sursa = NULL;
	
	for (int i = 0; i < n - 1; i++) {
		nod* u = new nod();
		nod* v = new nod();
		scanf("%i", &u->index);
		u->index--;
		u->distanta = -1;
		scanf("%i", &v->index);
		v->index--;
		v->distanta = -1;
		vecini[u->index].push_back(v);
		vecini[v->index].push_back(u);
		sursa = u;
	}
	int maxDistance = 0;
	sursa->distanta = 0;
	nod* x = bfs(vecini, sursa, &maxDistance);
	x->distanta = 0;
	nod* y = bfs(vecini, x, &maxDistance);
	printf("%i", maxDistance + 1);

	fclose(stdin);
	fclose(stdout);
	return 0;
}