Cod sursa(job #2266123)

Utilizator FilpTeodorFilp Teodor FilpTeodor Data 22 octombrie 2018 11:47:31
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

struct Node{
	int value;
	int distanceFromSource;
};
int verticesNumber,  edgeNumber;
vector<int> *adj;
void addEdge(int , int );
Node bfs(int );
int main(){

	ifstream read("darb.in");
	ofstream write("darb.out");

	read>>verticesNumber;
	adj = new vector<int>[verticesNumber];
	edgeNumber = verticesNumber - 1;
	for(int i=0; i<edgeNumber; i++)
	{
		int x, y;
		read>>x>>y;
		x--;
		y--;
		addEdge(x, y);

	}

	Node oneEnd = bfs(0);

	Node anotherEnd = bfs(oneEnd.value);

	write<<anotherEnd.distanceFromSource;



	return 0;
}

Node bfs(int s){
	bool *visited = new bool[verticesNumber];

	for(int i=0; i<verticesNumber; i++)
		visited[i] = false;

	queue<Node> Q;
	Node sourceNode;
	sourceNode.value = s;
	sourceNode.distanceFromSource = 1;
	Q.push(sourceNode);
	visited[s] = true;
	int distance;
	while(!Q.empty()){

		sourceNode = Q.front();
		distance = sourceNode.distanceFromSource;
		Q.pop();

		vector<int>::iterator it = adj[sourceNode.value].begin();

		for(; it!=adj[sourceNode.value].end(); ++it){
			if(!visited[(*it)]){
				visited[(*it)] = true;
				Node aux;
				aux.value = (*it);
				aux.distanceFromSource = sourceNode.distanceFromSource + 1;

				Q.push(aux);
			}
		}

	}
	Node endNode;
	endNode.value = sourceNode.value;
	endNode.distanceFromSource = distance;

	return endNode;

}

void addEdge(int v, int w){
	adj[v].push_back(w);
	adj[w].push_back(v);
}