Cod sursa(job #1702962)

Utilizator bogdandvDamaschin Bogdan-Valentin bogdandv Data 15 mai 2016 20:43:19
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include<queue>
using namespace std;

long int m,n;
vector< vector <long int> > graph;
vector<bool> visited;
vector<long int> dist;
queue<long int> q;
int ultim;
void bfs(long int vertex)
{
    long int element;
    if(vertex<0 || vertex>n-1)
        return;
    q.push(vertex);
    visited[vertex]=true;
    while(!q.empty())
    {
        element=q.front();
        ultim=element;
        //cout<<element<<" ";
        for(long int i=0;i<graph[element].size();i++)
            {if(!visited[graph[element][i]])
                {q.push( graph[element][i]);
                dist[graph[element][i]]=dist[element]+1;
                }
             visited[graph[element][i]]=true;
            }
        q.pop();
    }
}

int main()
{long int nr;
    ifstream f("raza.in");
    ofstream g("raza.out");
    f>>n;
    m=n-1;
    graph.resize(n);
    visited.resize(n,false);
    dist.resize(n,-1);
    long int x,y;
    for(long int i=0;i<m;i++)
    {
        f>>x>>y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    nr=1;
    //cout<<nr;
    dist[nr-1]=0;
    bfs(nr-1);
   // cout<<ultim+1<<" "<<dist[ultim]<<" ";
    for(int i=0;i<=n;i++)
        {visited[i]=false;
        dist[i]=-1;
        }
    dist[ultim]=0;
    //cout<<"!";
    bfs(ultim);
    g<<dist[ultim]+1;

    return 0;
}