Cod sursa(job #2603873)

Utilizator chriss_b_001Cristian Benghe chriss_b_001 Data 21 aprilie 2020 08:29:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

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

int n, m;
bool viz1[100001], viz2[100001];
int maxx, nfin;

struct nod
{
    int val;
    nod *urm;
};

nod *L[100001];

void add_nod(int x, int y)
{
    nod *p = new nod;
    p->val = y;
    p->urm = L[x];
    L[x] = p;
}

void citire()
{
    int x, y;
    f >> n;
    m = n - 1;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y;
        add_nod(x, y);
        add_nod(y, x);
    }
}

void DFS(int i, bool viz[], int crt)
{
    if(crt > maxx)
    {
        nfin = i;
        maxx = crt;
    }
    viz[i] = 1;
    for(nod *p = L[i]; p != NULL; p = p->urm)
        if(!viz[p->val])
            DFS(p->val, viz, crt + 1);
}


int main()
{
    citire();
    DFS(1, viz1, 0);
    maxx = 0;
    DFS(nfin, viz2, 0);
    g << maxx + 1;
    return 0;
}