Cod sursa(job #2195784)

Utilizator Alex_AmarandeiAmarandei Matei Alexandru Alex_Amarandei Data 17 aprilie 2018 13:23:40
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

vector <int> a[100005];
queue <int> q;
int n, last, dist[100005], diametru;
bool f[100005];

void read();
void bfs1(int start);
void bfs2(int start);
void write();

int main()
{
	read();
	bfs1(1);
	bfs2(last);
	write();

	return 0;
}

void read()
{
	int i, x, y;
	fin >> n;

	for (i = 1; i < n; i++)
	{
		fin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

void bfs1(int start)
{
	int x, i; q.push(start); dist[start] = 1;
	while (!q.empty())
	{
		x = q.front(); q.pop();
		for (i = 0; i < a[x].size(); i++)
			if (!f[a[x][i]])
			{
				q.push(a[x][i]); f[a[x][i]] = true;
				dist[a[x][i]] = dist[x] + 1;
				diametru = dist[a[x][i]];
			}
	}
	last = x;
}

void bfs2(int start)
{
	int x, i; q.push(start); dist[start] = 1;
	while (!q.empty())
	{
		x = q.front(); q.pop();
		for (i = 0; i < a[x].size(); i++)
			if (f[a[x][i]])
			{
				q.push(a[x][i]); f[a[x][i]] = false;
				dist[a[x][i]] = dist[x] + 1;
				diametru = dist[a[x][i]];
			}
	}

	last = x;
}

void write()
{
	fout << diametru << '\n';
}