Cod sursa(job #2173631)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 15 martie 2018 23:14:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define nmax 100005
ifstream f("darb.in");
ofstream g("darb.out");

vector<int>Q[nmax];

int n,longestseq[nmax],viz[nmax],diameter;

void read()
{
    f>>n;
    for (int i=1; i<=n; ++i)
    {
        int e1,e2;
        f>>e1>>e2;
        Q[e1].push_back(e2);
        Q[e2].push_back(e1);
    }
}

void dfs(int nod)
{
    longestseq[nod]=1;
    viz[nod]=true;
    int mx1=0,mx2=0;
    for (auto w:Q[nod])
    {
        if (viz[w])
            continue;
        dfs(w);
        longestseq[nod]=max(longestseq[nod],longestseq[w]+1);
        if (longestseq[w]>mx1)
        {
            mx2=mx1;
            mx1=longestseq[w];
        }
        else if (longestseq[w]>mx2)
            mx2=longestseq[w];
    }
    diameter=max(diameter,mx1+mx2+1);
}

void solve()
{
    dfs(1);
    g<<diameter;
}

int main()
{
    read();
    solve();
    return 0;
}