Pagini recente » Cod sursa (job #1843207) | Cod sursa (job #2291024) | Cod sursa (job #2111710) | Cod sursa (job #972527) | Cod sursa (job #2797148)
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n, leaves[100001];
vector<vector<int>> adjacentList(100001);
int get_leaf() {
for (int i = 1; i <= n; ++i) {
if (leaves[i] == 1) {
return i;
}
}
}
void initialize_array(int arr[100001], int element) {
for (int i = 0; i <= n; ++i) {
arr[i] = element;
}
}
void dfs(int current_node, int visited[100001], pair<int, int> &furthestLeaf, int distance) {
if (furthestLeaf.second < distance) {
furthestLeaf.first = current_node; // update the node
furthestLeaf.second = distance; // update the distance
}
for (int i = 0; i < adjacentList[current_node].size(); ++i) {
int adjacentNode = adjacentList[current_node][i];
if (!visited[adjacentNode]) {
visited[adjacentNode] = 1;
//nodes.push(adjacentNode)
dfs(adjacentNode, visited, furthestLeaf, distance + 1);
}
}
}
int main() {
f >> n;
for (int i = 1; i < n; ++i) {
int x, y;
f >> x >> y;
adjacentList[x].push_back(y);
adjacentList[y].push_back(x);
++leaves[x];
++leaves[y];
}
int start_leaf = get_leaf();
int visited[100001];
initialize_array(visited, 0);
pair<int, int> furthestLeaf (start_leaf, 1);
visited[start_leaf] = 1;
dfs(start_leaf, visited, furthestLeaf, 1);
//cout << furthestLeaf.first << " " << furthestLeaf.second << "\n";
initialize_array(visited, 0);
furthestLeaf.second = 1;
dfs(furthestLeaf.first, visited, furthestLeaf, 1);
g << furthestLeaf.second << "\n";
return 0;
}