Pagini recente » Cod sursa (job #1751210) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 72 | Cod sursa (job #2628926) | Cod sursa (job #3287405) | Cod sursa (job #3167728)
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 1e5 + 1;
vector<int> G[NMAX];
bool nonroot[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);
nonroot[y] = true;
}
int max1, max2, longest_path, root;
max1 = max2 = 0;
root = 1;
while (nonroot[root])
root++;
for (int i = 0; i < (int)G[root].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;
}