Cod sursa(job #1710948)

Utilizator teodorauTeodora Untaru teodorau Data 30 mai 2016 06:57:54
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

vector<int> graph[100001];
queue<int> q;
int n,contor[100001],visited[100001],last,diametru;

void BFS(int vertex)
{
    q.push(vertex);
    contor[vertex]=1;
    visited[vertex]=1;
    int i,element;
    while(!q.empty())
        {
        element=q.front();
        for(i=0;i<graph[element].size();i++){
            if(visited[graph[element][i]]==0)
                {
                q.push(graph[element][i]);
                contor[graph[element][i]]=contor[element]+1;
                visited[graph[element][i]]=1;

                diametru=contor[graph[element][i]];
                last=graph[element][i];
                }
        }
        q.pop();
    }
}



int main()
{
    int i,x,y;
    f>>n;
    for(i=0;i<n-1;i++)
    {
        f>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    BFS(1);
    BFS(last);
    g<<diametru;
    /*g<<"Raza "<<diametru/2;
*/
    return 0;
}