Cod sursa(job #2204922)

Utilizator vladut_programatorVladutz vladut_programator Data 17 mai 2018 11:02:46
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <list>

using namespace std;

int n, diam;
vector <list <int> > l_ad;
vector <bool> vis;
vector <int> h;

int _dfs(int curr)
{
    int deepest = h[curr], max1 = 0, max2 = 0, ld = 0;
    vis[curr] = true;

    for (int neigh : l_ad[curr])
        if (!vis[neigh])
        {
            h[neigh] = h[curr] + 1;
            int low = _dfs(neigh);

            if (low > deepest)
                deepest = low;

            low = low - h[curr];

            if (low > max1)
            {
                if (max1 > max2)
                    max2 = max1;
                max1 = low;
            }
            else if (low > max2)
                max2 = low;
        }

    ld = max1 + max2;

    diam = max(diam, ld);

    return deepest;
}

void DFS(int root)
{
    vis.resize(n + 1);
    h.resize(n + 1);
    _dfs(root);
}

int main()
{
    ifstream in ("darb.in");
    ofstream out ("darb.out");
    in >> n;
    l_ad.resize(n + 1);

    int j, k;
    for (int i = 1; i <= n - 1; i++)
    {
        in >> j >> k;
        l_ad[j].push_back(k);
        l_ad[k].push_back(j);
    }

    DFS(1);

    out << diam + 1;

    in.close();
    out.close();
}