Pagini recente » Cod sursa (job #2713971) | Cod sursa (job #46478) | Cod sursa (job #234322) | Cod sursa (job #1693501) | Cod sursa (job #2871238)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX_NR_NODES 100001
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector<int> adjancency_list[MAX_NR_NODES];
queue<int> neighbours;
int distances[MAX_NR_NODES];
void find_max_length_chain(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; // I only need this node for the first bfs traversal so I know which node is farthest from the start_node so I can use this "last node" as the start node for the second bfs
find_max_length_chain(1, last_node, max_length_chain);
find_max_length_chain(last_node, last_node, max_length_chain);
fout << max_length_chain + 1;
return 0;
}