Cod sursa(job #1666016)

Utilizator StanescuVictorStanescu Victor Laurentiu StanescuVictor Data 27 martie 2016 16:14:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.5 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>

typedef unsigned int uint;

class Graph
{
public:
	virtual ~Graph() { }
	
	virtual uint getDegree(uint vertex) const = 0;
	virtual std::vector<uint> breadthFirstSearch(uint vertex) const = 0;
	virtual std::vector<int> getRoadDistance(uint vertex) const = 0;

protected:
	std::vector<std::vector<uint>> adjacencyList;
	uint vertices, edges;

	Graph() : vertices(0), edges(0), adjacencyList(0) { }
	Graph(uint _vertices) : vertices(_vertices), edges(_vertices - 1), adjacencyList(_vertices) { }
	Graph(uint _vertices, uint _edges, std::vector<std::vector<uint>> _adjacencyList) :
		vertices(_vertices), edges(_edges), adjacencyList(_adjacencyList) { }

	bool isValidVertex(uint vertex) const;
};

bool Graph::isValidVertex(uint vertex) const
{
	if (vertex < 0 || vertex > vertices - 1)
		return false;

	return true;
}

class UndirectedGraph : public Graph
{
public:
	UndirectedGraph() : Graph() { }
	UndirectedGraph(std::ifstream& ifs);
	UndirectedGraph(const UndirectedGraph& source) : Graph(source.vertices, source.edges, source.adjacencyList) { }
	~UndirectedGraph() { };

	uint getDegree(uint vertex) const;
	std::vector<uint> breadthFirstSearch(uint vertex) const;
	std::vector<int> getRoadDistance(uint vertex) const;

protected:
	UndirectedGraph(uint _vertices) : Graph(_vertices) { }
};

UndirectedGraph::UndirectedGraph(std::ifstream& ifs)
{
	ifs >> vertices >> edges;
	adjacencyList.resize(vertices);

	for (uint i = 0; i < edges; i++)
	{
		uint x, y;
		ifs >> x >> y;
		x--; y--;
		adjacencyList[x].push_back(y);
		adjacencyList[y].push_back(x);
	}
}

uint UndirectedGraph::getDegree(uint vertex) const
{
	if (!isValidVertex(vertex))
		return 0;

	return adjacencyList[vertex].size();
}

std::vector<uint> UndirectedGraph::breadthFirstSearch(uint vertex) const
{
	if (!isValidVertex(vertex))
		return std::vector<uint>();

	std::vector<bool> visited(vertices);
	std::queue<uint> queue;
	std::vector<uint> connectedComponent;

	queue.push(vertex);
	visited[vertex] = true;
	connectedComponent.push_back(vertex);

	while (!queue.empty())
	{
		uint element = queue.front();

		for (uint i = 0; i < getDegree(element); i++)
			if (!visited[adjacencyList[element][i]])
			{
				connectedComponent.push_back(adjacencyList[element][i]);
				queue.push(adjacencyList[element][i]);
				visited[adjacencyList[element][i]] = true;
			}
		queue.pop();
	}

	return connectedComponent;
}

std::vector<int> UndirectedGraph::getRoadDistance(uint vertex) const
{
	if (!isValidVertex(vertex))
		return std::vector<int>();

	std::vector<bool> visited(vertices);
	std::queue<uint> queue;
	std::vector<int> roadDistance(vertices, -1);

	queue.push(vertex);
	visited[vertex] = true;
	roadDistance[vertex] = 0;

	while (!queue.empty())
	{
		uint element = queue.front();

		for (uint i = 0; i < getDegree(element); i++)
			if (!visited[adjacencyList[element][i]])
			{
				roadDistance[adjacencyList[element][i]] = roadDistance[element] + 1;
				queue.push(adjacencyList[element][i]);
				visited[adjacencyList[element][i]] = true;
			}
		queue.pop();
	}

	return roadDistance;
}

class Tree : public UndirectedGraph
{
public:
	Tree() : UndirectedGraph() { }
	Tree(uint _vertices);
	Tree(std::ifstream& ifs);

	uint getDiameter() const;
};

Tree::Tree(uint _vertices) : UndirectedGraph(_vertices)
{
	for (uint i = 0; i < vertices - 1; i++)
	{
		uint x, y;
		std::cin >> x >> y;
		adjacencyList[x].push_back(y);
		adjacencyList[y].push_back(x);
	}
}

Tree::Tree(std::ifstream& ifs)
{
	ifs >> vertices;
	adjacencyList.resize(vertices);

	for (uint i = 0; i < vertices - 1; i++)
	{
		uint x, y;
		ifs >> x >> y;
		x--; y--;
		adjacencyList[x].push_back(y);
		adjacencyList[y].push_back(x);
	}
}

uint Tree::getDiameter() const
{
	srand((uint)time(NULL));
	uint vertex = rand() % vertices;
	uint firstLeaf = *breadthFirstSearch(vertex).rbegin();								// The last element discovered by BFS.
	std::vector<int> roadDistance = getRoadDistance(firstLeaf);							// Get the distance from firstLeaf to all vertices in the tree.
	uint diameter = *std::max_element(roadDistance.cbegin(), roadDistance.cend()) + 1;	// Set the diameter to the highest value from roadDistance + 1.

	return diameter;
}


int main()
{
	std::ifstream f("darb.in");
	std::ofstream g("darb.out");
	Tree tree(f);

	g << tree.getDiameter();

	return 0;
}