Cod sursa(job #1690992)

Utilizator AnaMariaPintilieAna Maria Pintilie AnaMariaPintilie Data 16 aprilie 2016 15:45:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector <vector <int> > graph;
vector <int> visited;
int length=-1;

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

	queue <int> q;
	int element,i;
	q.push(vertex);
	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;
                if(visited[graph[element][i]]>length) length=visited[graph[element][i]];
            }
        }

         q.pop();

	}
	return element;
}

int main()
{
    int x,y,i;
	ifstream fin("darb.in");
	ofstream fout("darb.out");
	fin>>n;
	graph.resize(n);
	visited.resize(n,-1);

	for(i=0;i<n-1;i++)
    {
        fin>>x>>y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    fin.close();
    int first,last;
    first=bfs(0);
    visited.clear();
    visited.resize(n, -1);
    last=bfs(first);
    fout<<length+1;
    fout.close();
	return 0;
}