Pagini recente » Cod sursa (job #652382) | Cod sursa (job #131857) | Cod sursa (job #1181843) | Cod sursa (job #1748895) | Cod sursa (job #1762611)
#include <fstream>
#include <vector>
#include <queue>
class SimpleTree
{
int mSize;
std::vector<int> *edges; //rooted at 1
public:
SimpleTree(int size)
{
mSize = size + 1;
edges = new std::vector<int>[mSize];
}
std::vector<int> computeDistancesFromSource(int source)
{
std::vector<int> distances(mSize, -1);
if (source <= 0 || source >= mSize) return distances;
std::queue<int> bfs_queue;
distances[source] = 0;
bfs_queue.push(source);
while (!bfs_queue.empty()) {
int current_vertex = bfs_queue.front();
bfs_queue.pop();
for (int vertex : edges[current_vertex]) {
if (distances[vertex] == -1) {
distances[vertex] = distances[current_vertex] + 1;
bfs_queue.push(vertex);
}
}
}
return distances;
}
void addEdge(int a, int b)
{
edges[a].push_back(b);
edges[b].push_back(a);
}
int getDiameter()
{
auto distances = computeDistancesFromSource(1);
int furthest_vertex = 1;
for (int i = 2; i < mSize; ++i) {
if (distances[i] > distances[furthest_vertex]) furthest_vertex = i;
}
distances = computeDistancesFromSource(furthest_vertex);
int diameter = 0;
for (int distance : distances) {
if (distance > diameter) diameter = distance;
}
return diameter + 1;
}
};
int main()
{
std::ifstream input("darb.in");
std::ofstream output("darb.out");
int n;
input >> n;
SimpleTree tree(n);
for(int i = 1; i < n; ++i) {
int a, b;
input >> a >> b;
tree.addEdge(a, b);
}
output << tree.getDiameter() << '\n';
}