Pagini recente » Cod sursa (job #2675902) | Cod sursa (job #2033762) | Cod sursa (job #2232772) | Cod sursa (job #3123541) | Cod sursa (job #2224996)
#include <fstream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef vector<vector<int>> Graph;
const string IN_FILE = "darb.in";
const string OUT_FILE = "darb.out";
vector<int> bfs(const Graph& graph, const int source) {
queue<int> q;
auto distances = vector<int>(int(graph.size()), -1);
distances[source] = 0;
for (q.push(source); !q.empty(); q.pop()) {
const int u = q.front();
for (const auto& v : graph[u]) {
if (distances[v] == -1) {
distances[v] = distances[u] + 1;
q.push(v);
}
}
}
return distances;
}
int findMaxIndex(const vector<int>& values) {
int index = -1;
for (int i = 0; i < int(values.size()); i++) {
index = index == -1 || values[i] > values[index] ? i : index;
}
return index;
}
int getDiameter(const Graph& tree) {
const int from = findMaxIndex(bfs(tree, 0));
const auto distances = bfs(tree, from);
const int to = findMaxIndex(distances);
return distances[to];
}
inline void addEdge(Graph& graph, const int u, const int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
Graph readTree() {
ifstream in(IN_FILE);
int n;
in >> n;
auto tree = Graph(n);
for (int i = 1; i < n; i++) {
int u, v;
in >> u >> v;
addEdge(tree, u - 1, v - 1);
}
in.close();
return tree;
}
void writeDiameter(const int diameter) {
ofstream out(OUT_FILE);
out << diameter + 1 << "\n";
out.close();
}
int main() {
const auto& tree = readTree();
const int diameter = getDiameter(tree);
writeDiameter(diameter);
return 0;
}