Pagini recente » Cod sursa (job #34910) | Cod sursa (job #211704) | Cod sursa (job #2668230) | Cod sursa (job #2438572) | Cod sursa (job #1094290)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
class Tree {
public:
static const int NIL = -1;
Tree(const int _v = 0):
v(_v),
edges(vector< vector<int> >(_v, vector<int>())) {}
int V() const {
return v;
}
vector<int>::const_iterator EdgesBegin(const int x) const {
return edges[x].cbegin();
}
vector<int>::const_iterator EdgesEnd(const int x) const {
return edges[x].cend();
}
void AddEdge(const int x, const int y) {
edges[x].push_back(y);
edges[y].push_back(x);
}
int GetDiameter() const {
int x = 0, diameter = 0;
vector<int> distances;
BFS(x, distances);
for (int y = 0; y < v; ++y)
if (distances[y] > distances[x])
x = y;
BFS(x, distances);
for (int y = 0; y < v; ++y)
diameter = max(diameter, distances[y]);
return diameter;
}
private:
int v;
vector< vector<int> > edges;
void BFS(const int source, vector<int> &distances) const {
distances = vector<int>(v, -1);
queue<int> q;
distances[source] = 0;
q.push(source);
for (; !q.empty(); q.pop()) {
int x = q.front();
for (const auto &y: edges[x]) {
if (distances[y] == -1) {
distances[y] = distances[x] + 1;
q.push(y);
}
}
}
}
};
Tree T;
int Diameter;
void Solve() {
Diameter = T.GetDiameter();
}
void Read() {
ifstream in("darb.in");
int v;
in >> v;
T = Tree(v);
for (int i = 0; i < v - 1; ++i) {
int x, y;
in >> x >> y;
--x;
--y;
T.AddEdge(x, y);
}
in.close();
}
void Print() {
ofstream out("darb.out");
out << Diameter << "\n";
out.close();
}
int main() {
Read();
Solve();
Print();
return 0;
}