Pagini recente » Borderou de evaluare (job #1053463) | Borderou de evaluare (job #172950) | Borderou de evaluare (job #441488) | Borderou de evaluare (job #156660) | Cod sursa (job #3198438)
// Tree Diameter - CSES
#include <iostream>
#include <vector>
#include <fstream>
struct Graph {
private:
std::vector<std::vector<int>> adj;
std::vector<int> depth;
int size;
void dfs_depth(int node, int root = 0) {
depth[node] = 1 + depth[root];
for (const auto &x: adj[node]) {
if (x == root) continue;
dfs_depth(x, node);
}
}
public:
explicit Graph(int size) : size(size) {
adj.resize(size + 1);
depth.resize(size + 1);
}
void add_edge(int x, int y) {
adj[x].push_back(y);
adj[y].push_back(x);
}
int get_diameter() {
depth[0] = -1;
dfs_depth(1);
int next = 1;
for (int i = 2; i <= size; ++i) {
if (depth[i] > depth[next]) next = i;
}
dfs_depth(next);
int max = 0;
for (int i = 1; i <= size; ++i) max = std::max(max, depth[i]);
return max;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::ifstream input("darb.in");
std::ofstream output("darb.out");
int n;
std::cin >> n;
Graph tree(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
std::cin >> a >> b;
tree.add_edge(a, b);
}
std::cout << tree.get_diameter();
return 0;
}