Cod sursa(job #2195797)

Utilizator theodor.vladTheodor Vlad theodor.vlad Data 17 aprilie 2018 13:28:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <utility>

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

pair<int, int> dfs1(int);
int dfs2(int);
void citire();

int n, x, y;
bool viz[100005];
vector<int> G[100005];

int main()
{
    citire();
    pair<int, int> p = dfs1(1);
    fout << 1 + dfs2(p.first) << '\n';
    return 0;
}

int dfs2(int rad)
{
    int maxim = 0, rez;
    viz[rad] = false;

    for (unsigned i = 0; i < G[rad].size(); i++)
        if (viz[G[rad][i]])
        {
            rez = 1 + dfs2(G[rad][i]);
            if (rez > maxim)
                maxim = rez;
        }

    return maxim;
}

pair<int, int> dfs1(int rad)
{
    pair<int, int> maxim, p;
    maxim.first = rad; maxim.second = 0;
    viz[rad] = true;

    for (unsigned i = 0; i < G[rad].size(); i++)
        if (!viz[G[rad][i]])
        {
            p = dfs1(G[rad][i]);
            p.second++;
            if (p.second > maxim.second)
                maxim = p;
        }

    return maxim;
}

void citire()
{
    fin >> n;
    for (int i = 1; i < n; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}