Cod sursa(job #1699935)

Utilizator madalina41724Madalina Marin madalina41724 Data 8 mai 2016 21:04:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

int m, n;
vector <vector <int> > graph;
vector <int> visited;
ifstream f("darb.in");
ofstream h("darb.out");

int poz1, poz2;

void bfs(int vertex)
{
    if (vertex<0 || vertex>n - 1) return;

    queue <int> q;
    int element;
    unsigned int i;

    q.push(vertex);

    for(i=0;i<(unsigned int)n;i++) visited[i]=-1;
    visited[vertex] = 0;

    while (!q.empty())
    {
        element = q.front();
        for (i = 0; i < graph[element].size(); i++)
            if (visited[graph[element][i]]==-1)
            {
                q.push(graph[element][i]);
                visited[graph[element][i]] = visited[element]+1;
            }
        q.pop();
    }

}


int main()
{
    int x, y, i,nod;
    f >> n;
    m=n-1;
    nod=n;
    nod--;
    graph.resize(n);
    visited.resize(n, false);

    for (i = 0; i<m; i++)
    {
        f >> x >> y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    bfs(nod);

    poz1=0; poz2=0;
    for(i=1;i<n;i++)
        if(visited[i]>visited[poz1]) poz1=i;

    bfs(poz1);

    for(i=0;i<n;i++)
        if(visited[i]>visited[poz2]) poz2=i;

    h << visited[poz2]+1;

    f.close();
    h.close();
    return 0;
}