Pagini recente » Cod sursa (job #2170549) | Cod sursa (job #931364) | Cod sursa (job #2270165) | Cod sursa (job #2426208) | Cod sursa (job #2863735)
#include <array>
#include <fstream>
#include <vector>
#include <queue>
enum class BfsTarget {
deepestNode, biggestDepth
};
constexpr size_t MAX_NODES = 100000;
size_t nodes;
std::array<std::vector<size_t>, MAX_NODES> edges;
template<BfsTarget bfsTarget>
size_t bfs (size_t start) {
std::queue<size_t> q({start});
std::vector<size_t> depth(nodes);
depth[start] = 1;
size_t nowNode = start;
while (!q.empty()) {
nowNode = q.front();
q.pop();
for (auto to: edges[nowNode]) {
if (depth[to] == 0) {
depth[to] = depth[nowNode] + 1;
q.emplace(to);
}
}
}
if constexpr (bfsTarget == BfsTarget::deepestNode) {
return nowNode;
} else if (bfsTarget == BfsTarget::biggestDepth) {
return depth[nowNode];
}
}
void readInput () {
std::ifstream file("darb.in");
file.exceptions(file.badbit | file.eofbit | file.failbit);
file >> nodes;
for (size_t i = 0; i != nodes - 1; ++ i) {
size_t x, y;
file >> x >> y;
-- x, -- y;
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
}
void writeAnswer (size_t diameter) {
std::ofstream file("darb.out");
file.exceptions(file.badbit | file.eofbit | file.failbit);
file << diameter;
}
int main () {
readInput();
const size_t deepestNode = bfs<BfsTarget::deepestNode>(0);
const size_t depth = bfs<BfsTarget::biggestDepth>(deepestNode);
writeAnswer(depth);
}