Cod sursa(job #2030898)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 2 octombrie 2017 14:35:05
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;

vector <int> G[Nmax];

int lung[Nmax],rasp[Nmax],n;

bool viz[Nmax];

ifstream f("darb.in");
ofstream g("darb.out");

void dfs(int x)
{
    vector <int> Sons;
    viz[x]=1;
    for(auto it : G[x])
        if(!viz[it])
            {
                Sons.push_back(it);
                dfs(it);
            }
    int maxim=0, maxim2=0;
    for(auto it: Sons)
        {
            if(lung[it]>maxim)
            {
                maxim2=maxim;
                maxim=lung[it];
            }
            else if(lung[it]>maxim2)
                maxim2=lung[it];

        }
    lung[x]=maxim+1;
    rasp[x]=maxim+maxim2+1;
}

int main()
{
    int i;
    f>>n;
    for(i=1; i<=n; i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(n);
    /*for(i=1; i<=n; i++)
        g<<lung[i]<<" ";
    g<<'\n';
    for(i=1; i<=n; i++)
        g<<rasp[i]<<" ";*/
    g<<rasp[n];
    return 0;
}