Pagini recente » Cod sursa (job #131027) | Cod sursa (job #2477666) | Cod sursa (job #678443) | Cod sursa (job #1787251) | Cod sursa (job #2797181)
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n;
int is_leaf[100001];
struct node {
int value;
vector<int> adjacentNodes; // there will be stored maximum 3 nodes (2 children, 1 father)
bool visited = false;
} nodes[100001];
int get_first_leaf() {
for (int i = 1; i <= n; ++i) {
if (is_leaf[i] == 1) {
return i;
}
}
}
void dfs(int current_node, int distance, pair<int, int> &furthestLeaf) {
if (distance > furthestLeaf.second) {
furthestLeaf.first = current_node;
furthestLeaf.second = distance;
}
nodes[current_node].visited = true;
vector<int> children (nodes[current_node].adjacentNodes.begin(), nodes[current_node].adjacentNodes.end());
for (int i = 0; i < children.size(); ++i) {
int child = nodes[children[i]].value;
if (nodes[child].visited == false) {
dfs(child, distance + 1, furthestLeaf);
}
}
}
int main() {
f >> n;
for (int i = 1; i < n; ++i) {
int x, y;
f >> x >> y;
nodes[x].value = x;
nodes[y].value = y;
nodes[x].adjacentNodes.push_back(y);
nodes[y].adjacentNodes.push_back(x);
++is_leaf[x];
++is_leaf[y];
}
pair<int, int> furthestNLeaf (get_first_leaf(), 1); // first element it's the node, the second it's the distance
dfs(furthestNLeaf.first, 1, furthestNLeaf);
for (int i = 1; i <= n; ++i) {
nodes[i].visited = false;
}
dfs(furthestNLeaf.first, 1, furthestNLeaf);
g << furthestNLeaf.second << "\n";
return 0;
}