Cod sursa(job #1993343)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 22 iunie 2017 18:21:26
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>

using namespace std;

vector<int> v[100010], sols;
int n, mx, d[100010];
bool ok[100010];

void dfs(int pred, int nod)
{
    ok[nod] = 1;
    d[nod] = d[pred] + 1;
    mx = max(mx, d[nod]);
    for (unsigned i = 0; i < v[nod].size(); ++i)
        if(v[nod][i] != pred && !ok[v[nod][i]])
            dfs(nod, v[nod][i]);
}

int main()
{
    ifstream fin ("darb.in");
    ofstream fout ("darb.out");
    fin >> n;
    for (int i = 1; i < n; ++i){
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (unsigned i = 0; i < v[1].size(); ++i){
        mx = 0;
        dfs(1, v[1][i]);
        sols.push_back(mx);
    }
    if(sols.size() == 1)
        fout << sols[0] + 1 << "\n";
    else{
        int mx1 = max(sols[0], sols[1]), mx2 = min(sols[0], sols[1]);
        for (unsigned i = 2; i < sols.size(); ++i)
            if(sols[i] > mx1)
                mx2 = mx1,
                mx1 = sols[i];
            else if (sols[i] > mx2)
                mx2 = sols[i];
        fout << mx1 + mx2 + 1 << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}