Pagini recente » Cod sursa (job #451045) | Cod sursa (job #2062154) | Cod sursa (job #1327699) | Cod sursa (job #237310) | Cod sursa (job #2865481)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector<int> adjancency_list[100001];
queue<int> neighbours;
int distances[100001];
void bfs_traversal(int start_node, int &last_node, int& max_length_chain) {
memset(distances, 0, sizeof distances);
neighbours.push(start_node);
while (!neighbours.empty()) {
int current_node = neighbours.front();
int current_nr_neighbours = adjancency_list[current_node].size();
last_node = current_node;
neighbours.pop();
for (int i = 0; i < current_nr_neighbours; ++i) {
int neighbour = adjancency_list[current_node][i];
if (!distances[neighbour] && neighbour != start_node) {
distances[neighbour] = distances[current_node] + 1;
max_length_chain = max(max_length_chain, distances[neighbour]);
neighbours.push(neighbour);
}
}
}
}
int main() {
int nr_nodes;
fin >> nr_nodes;
for (int i = 1; i < nr_nodes; ++i) {
int node_1, node_2;
fin >> node_1 >> node_2;
adjancency_list[node_1].push_back(node_2);
adjancency_list[node_2].push_back(node_1);
}
int max_length_chain = 1;
int last_node = 0;
bfs_traversal(1, last_node, max_length_chain);
bfs_traversal(last_node, last_node, max_length_chain);
fout << max_length_chain + 1;
return 0;
}