Cod sursa(job #2425712)

Utilizator antracodsAntracod antracods Data 24 mai 2019 23:56:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 100005;
vector <int> Graf[NMAX];
queue <int> myQueue;

int sol[NMAX];
int n;

void bfs(int start)
{
    myQueue.push(start);
    sol[start]=1;
    while(myQueue.empty()==false)
    {
        int node = myQueue.front();
        myQueue.pop();
        int p = Graf[node].size();
        for(int i=0; i<p; i++)
        {
            int selected_node = Graf[node][i];
            if(sol[selected_node]==0)
            {
                sol[selected_node] = sol[node]+1;
                myQueue.push(selected_node);
            }

        }
    }
}

void citeste()
{
    in>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        in>>x>>y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }
}

int afis()
{
    int xsol = 0;
    for(int i=1;i<=n;i++)
    {
        if(sol[i]>xsol)
        {
            xsol = sol[i];
        }
    }
    return xsol;
}

void reset_sol()
{
    for(int i=1;i<=n;i++)
    {
        sol[i] = 0;
    }
}

int main()
{
    citeste();

    bfs(1);
    int firstbest = 1;
    for(int i=2;i<=n;i++)
    {
        if(sol[i]>sol[firstbest])
            firstbest = i;
    }

    reset_sol();

    bfs(firstbest);

    out<<afis();

}