Cod sursa(job #1707903)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 26 mai 2016 08:29:21
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n;
vector<int> arbore[100005];
queue<int> coada;
bool vizitati[100005];
int costuri[100005];

void BFS(int s)
{
    int x;
    while(!coada.empty())
    {
        x=coada.front();
        coada.pop();
        for(int i=0;i<arbore[x].size();i++)
        {
            if(!vizitati[arbore[x][i]])
            {
                coada.push(arbore[x][i]);
                vizitati[arbore[x][i]]=1;
                costuri[arbore[x][i]]=costuri[x]+1;
            }
        }
    }
}

int main()
{
    int x,y;
    int max_cost=0,m=1;
    in>>n;
    while(in>>x>>y)
    {
        arbore[x].push_back(y);
        arbore[y].push_back(x);
    }
    costuri[1]=0;
    vizitati[1]=1;
    coada.push(1);
    BFS(1);
    for(int i=1;i<=n;i++)
    {
        if(costuri[i]>max_cost)
        {
            max_cost=costuri[i];
            m=i;
        }
        costuri[i]=0;
        vizitati[i]=0;
    }
    //cout<<m<<" "<<max_cost<<endl;
    coada.push(m);
    vizitati[m]=1;
    BFS(m);
    max_cost=0;
    for(int i=1;i<=n;i++)
        if(costuri[i]>max_cost)
            max_cost=costuri[i];
    out<<max_cost+1;
    return 0;
}