Pagini recente » Cod sursa (job #3294444) | Cod sursa (job #1188386) | Cod sursa (job #1634590) | Cod sursa (job #151301) | Cod sursa (job #3167725)
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 1e5 + 1;
vector<int> G[NMAX];
int max(int a, int b) {
return a > b ? a : b;
}
int compute_longest_path(int node) {
int longest_path = 0;
for (int i = 0; i < (int)G[node].size(); i++) {
int next_node = G[node][i];
longest_path = max(longest_path, compute_longest_path(next_node));
}
return longest_path + 1;
}
int main()
{
FILE *fin, *fout;
fin = fopen("darb.in", "r");
fout = fopen("darb.out", "w");
int n, x, y;
fscanf(fin, "%d", &n);
for (int i = 0; i < n - 1; i++) {
fscanf(fin, "%d %d", &x, &y);
G[x].push_back(y);
}
int max1, max2, longest_path;
max1 = max2 = 0;
for (int i = 0; i < (int)G[1].size(); i++) {
longest_path = compute_longest_path(G[1][i]);
if (longest_path >= max1) {
max2 = max1;
max1 = longest_path;
} else if (longest_path >= max2) {
max2 = longest_path;
}
}
fprintf(fout, "%d\n", max1 + max2 + 1);
fclose(fin);
fclose(fout);
return 0;
}