Cod sursa(job #2982328)

Utilizator RobertlelRobert Robertlel Data 19 februarie 2023 22:37:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <map>
#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

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

int last , n , x , y , maxim , niv[100005] , viz[100005];

vector <int>v[100005];

void bfs (int nod)
{
    queue <int>c;
    viz[nod] = 1;
    c.push (nod);
    while (!c.empty())
    {
        int nod = c.front();
        last = nod;
        c.pop();
        for (int i = 0 ; i < v[nod].size () ; i++)
        {
            int vecin = v[nod][i];
            if (viz[vecin] == 0)
            {
               viz[vecin] = 1;
               c.push(vecin);
            }
        }
    }

}

void dfs (int nod)
{
    viz[nod] = 1;
    maxim = max (maxim , niv[nod]);
    for (int i = 0 ; i < v[nod].size () ; i++)
    {
        int vecin = v[nod][i];
        if (viz[vecin] == 0)
        {
            niv[vecin] = niv[nod] + 1;
            dfs (vecin);
        }
    }
}

int main()
{
    f >> n;
    for (int i = 1 ; i < n ; i++)
    {
        f >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
    bfs (1);
    memset (viz , 0 , sizeof (viz));
    dfs (last);
    g << maxim + 1;
    return 0;
}