Pagini recente » Cod sursa (job #1945165) | Cod sursa (job #825269) | Cod sursa (job #1543611) | Cod sursa (job #2594667) | Cod sursa (job #2723503)
#include <stdio.h>
#include <vector>
using namespace std;
void dfs(
int node, int prev_node, int distance,
vector<vector<int> > & tree, int & max_distance, int & furthest
) {
// leaf node
if (
(tree[node].size() == 0) ||
(tree[node].size() == 1 && tree[node][0] == prev_node)
) {
if (distance > max_distance) {
max_distance = distance;
furthest = node;
}
return;
}
for (int neighbor: tree[node]) {
if (neighbor == prev_node) {
continue;
}
dfs(neighbor, node, distance + 1, tree, max_distance, furthest);
}
}
int main() {
FILE * f;
int n, a, b;
f = fopen("darb.in", "r");
fscanf(f, "%d", &n);
vector<vector<int> > tree(n);
for (int i = 0; i < n - 1; ++i) {
fscanf(f, "%d%d", &a, &b);
--a;
--b;
tree[a].push_back(b);
tree[b].push_back(a);
}
fclose(f);
int max_distance = 1, furthest = 0;
dfs(0, -1, 1, tree, max_distance, furthest);
dfs(furthest, -1, 1, tree, max_distance, furthest);
f = fopen("darb.out", "w");
fprintf(f, "%d", max_distance);
fclose(f);
return 0;
}