Pagini recente » Cod sursa (job #224369) | Cod sursa (job #2620234) | Cod sursa (job #220401) | Cod sursa (job #2089272) | Cod sursa (job #2849017)
#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& 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();
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;
for (int node = 1; node <= nr_nodes; ++node) {
bfs_traversal(node, max_length_chain);
}
fout << max_length_chain + 1;
return 0;
}