Pagini recente » Cod sursa (job #218746) | Cod sursa (job #3254979) | Cod sursa (job #2956590) | Cod sursa (job #82736) | Cod sursa (job #3215869)
#include <fstream>
#include <queue>
#include <utility>
#include <vector>
/**
* A tree data structure.
*/
class Tree {
public:
/**
* Construct a tree with n nodes
* @param n the number of nodes
*/
void read(std::ifstream& in) {
in >> n;
adj.resize(n);
for (int i = 1; i < n; ++i) {
int x, y;
in >> x >> y;
// prefer 0-indexed nodes
x--;
y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
/*
* Compute the diameter of the tree
* @return the diameter of the tree
*/
int diameter() const {
const auto [_, x] = bfs(0); // ignore the distance, we only need the node with the maximum distance from the source
const auto [d, __] = bfs(x); // ignore the node, we only need the distance
return d;
}
private:
/**
* Perform a BFS starting from a given node
* @param source the source node
* @return a pair (d, x) where d is the maximum distance from source to any other node and x is the node with the maximum distance from source
*/
std::pair<int, int> bfs(int source) const {
std::vector<int> dist(n, -1); // dist[node] = -1 means node is not visited yet, otherwise it is the distance from source to node
std::queue<int> q; // used to perform BFS
q.push(source);
dist[source] = 0;
// compute distances from source to all other nodes
while (!q.empty()) {
const auto node = q.front();
q.pop();
for (const auto& neigh : adj[node]) {
if (dist[neigh] == -1) {
dist[neigh] = dist[node] + 1;
q.push(neigh);
}
}
}
// find the node with the maximum distance from source
const auto it = std::max_element(dist.begin(), dist.end());
return { *it + 1, static_cast<int>(it - dist.begin())};
}
int n; // number of nodes
std::vector<std::vector<int>> adj; // adjacency list: adj[ node ] = { x1, x2, ... }, where x1, x2, ... are the neighbors of node
};
int main() {
std::ifstream in("darb.in");
std::ofstream out("darb.out");
Tree tree;
tree.read(in);
out << tree.diameter() << '\n';
in.close();
out.close();
// for (const auto& [n, superprimes] : tests) {
// const auto result = generateAndCountSuperPrimes(n);
// if (superprimes == result) {
// std::cerr << "Test OK: n = " << n << " (superprimes = " << superprimes << ")" << std::endl;
// } else {
// std::cerr << "Test Failed: " << n << " expected " << superprimes << " got " << result << std::endl;
// }
// }
return 0;
}