Pagini recente » Cod sursa (job #3338672) | Cod sursa (job #2217093) | Cod sursa (job #3270099) | Cod sursa (job #2941417) | Cod sursa (job #2422346)
#include <iostream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <memory>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <functional>
using namespace std;
class Tree {
public:
Tree(int n, const vector<pair<int,int>>& edges) {
this->n = n;
this->e = vector<vector<int>>(n + 1);
for (auto p : edges) {
int x = p.first;
int y = p.second;
e[x].push_back(y);
e[y].push_back(x);
}
}
int CalculateDiameter() {
int x = TheFarestNode(CalculateDistances(1));
vector<int> dist = CalculateDistances(x);
int y = TheFarestNode(dist);
return dist[y] + 1;
}
private:
vector<int> CalculateDistances(int x) {
vector<int> dist(n + 1, 0);
vector<bool> viz(n + 1, 0);
Dfs(x, viz, dist);
return dist;
}
void Dfs(int x, vector<bool>& viz, vector<int>& dist) {
viz[x] = true;
for (auto y : e[x]) {
if (!viz[y]) {
dist[y] = dist[x] + 1;
Dfs(y, viz, dist);
}
}
}
int TheFarestNode(const vector<int>& dist) {
int best = 1;
for (int i = 1; i <= n; ++i) {
if (dist[i] > dist[best]) best = i;
}
return best;
}
int n;
vector<vector<int>> e;
};
class Solution {
public:
int TreeDiameter(int n, const vector<pair<int,int>>& edges) {
Tree tree(n, edges);
return tree.CalculateDiameter();
}
};
int main() {
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
int n, x, y;
vector<pair<int,int>> edges;
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i) {
scanf("%d %d", &x, &y);
edges.emplace_back(x,y);
}
Solution s;
printf("%d\n", s.TreeDiameter(n, edges));
return 0;
}