Cod sursa(job #2815066)

Utilizator mara.lucianaBelu Mara Luciana mara.luciana Data 9 decembrie 2021 01:19:56
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

//#define MAX_N 1000001

using namespace std;

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

#define NMAX 100001

//vector<int> l[MAX_N];
//queue<int> coada;
//int n,contor[MAX_N],viz[MAX_N],last,diametru;

int bfs(int nod, vector<vector<int>>& listaAd, int& diam)
{
    int viz[NMAX+1], d[NMAX+1], cap;
    queue<int> q;

    for(int i = 1; i <= NMAX; i++)
    {
        d[i] = 0;
        viz[i] = 0;
    }

    q.push(nod);
    d[nod] = 1;
    viz[nod] = 1;

    int x;

    while(!q.empty())
    {
        x = q.front();

        for(auto vecin:listaAd[x])
        {
            if(!viz[vecin])
            {
                q.push(vecin);
                viz[vecin] = 1;

                d[vecin] = d[x] + 1;

                diam = d[vecin];
                cap = vecin;
            }
        }

        q.pop();
    }

    return cap;
}

void citire(vector<vector<int>>& listaAd)
{
    int x, y, n;

    fin >> n;

    listaAd.resize(NMAX+1);

    for(int i = 0; i < n; i++)
    {
        fin >> x >> y;
        listaAd[x].push_back(y);
        listaAd[y].push_back(x);
    }
}

void darb_infoarena()
{
    vector<vector<int>> listaAd;
    int cap, diam;

    citire(listaAd);
    cap = bfs(1, listaAd, diam);
    bfs(cap, listaAd, diam);

    fout << diam;
}

int main()
{
    darb_infoarena();

    return 0;
}