Cod sursa(job #2640777)

Utilizator mex7Alexandru Valentin mex7 Data 8 august 2020 10:49:42
Problema Diametrul unui arbore Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> edgesList[100001];
int maxx;

void dfs(int current, int sum) {
    for (int i = 0; i < edgesList[current].size(); i++)
        dfs(edgesList[current][i], sum + 1);
    maxx = max(maxx, sum);
}

int main() {
    int numOfVertices, v, w, root = -1;

    fin >> numOfVertices;
    for (int i = 1; i < numOfVertices; i++) {
        fin >> v >> w;
        edgesList[v].push_back(w);

        if (root == -1)
            root = v;
    }

    int max1 = 0, max2 = 0;
    for (int i = 0; i < edgesList[1].size(); i++) {
        int current = 1;
        dfs(edgesList[1][i], current);

        if (maxx > max1)
            max2 = max1, max1 = maxx;
        else if (maxx > max2)
            max2 = maxx;
        maxx = 0;
    }

    if (max1 && max2)
        fout << max1 + max2 + 1;
    else 
        fout << max1 + max2;

    return 0;
}