Cod sursa(job #1666923)

Utilizator FernandoSandoiu Fernando Fernando Data 28 martie 2016 15:01:17
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <queue>
#include<iostream>

using namespace std;

int n;
int i, j;
vector< vector<int> > arb;
vector<int> visited;

int bfs(int vertex,int &max){

	if (vertex<0 || vertex>n - 1){
		return -1;
	}
	queue<int> q;
	int element;
	q.push(vertex);
	visited[vertex] = 0;
	while (!q.empty()){
		element = q.front();
		for (i = 0; i < arb[element].size(); i++)
		{
			if (visited[arb[element][i]] == -1)
			{
				q.push(arb[element][i]);
				visited[arb[element][i]] = visited[element] + 1;
				if (max < visited[arb[element][i]]) max = visited[arb[element][i]];
			}
		}
		q.pop();
	}
	return element;
}

int main()
{
	ifstream fin("darb.in");
	ofstream fout("darb.out");
	fin >> n;
	arb.resize(n);
	visited.resize(n, -1);
	int x, y;
	while (fin>>x>>y)
	{
		x--;
		y--;
		arb[x].push_back(y);
		arb[y].push_back(x);
	}
	int max,first,second;
	first = bfs(0, max);
	visited.clear();
	visited.resize(n, -1);
	second = bfs(first, max);
	fout << max+1;
	fin.close();
	fout.close();
	return 0;
}