Pagini recente » Cod sursa (job #1284228) | Cod sursa (job #1042440) | Cod sursa (job #2613384) | Cod sursa (job #2189147) | Cod sursa (job #1666016)
#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;
}