Cod sursa(job #1685573)

Utilizator andreilucaLuca Andrei andreiluca Data 11 aprilie 2016 18:56:31
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
FILE *in, *out;
vector<int> v[100000];
bool used[100000];
int n,max1;
void citire()
{
	
	in = fopen("darb.in","r");
	out = fopen("darb.out", "w");
	fscanf(in, "%d", &n);
	int x,y;
	for (int i = 0; i < n - 1; i++)
	{
		fscanf(in, "%d%d", &x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
};
int BFS(int nod)
{
	int ultim,x;
	queue<int> coada;
	coada.push(nod);
	used[nod] = 1;
	while (!coada.empty())
	{
		x = coada.front();
		
		coada.pop();
		for (int i = 0; i < v[x].size(); i++)
		{
			if (used[v[x][i]] == 0)
			{
				coada.push(v[x][i]);
				used[v[x][i]] = 1;
			}
		}
	}
	return x;
};
void DFS(int nod,int count)
{
	used[nod] = 1;
	if (max1 < count)
		max1 = count;
	for (int i = 0; i < v[nod].size(); i++)
	{
		if (used[v[nod][i]] == 0)
			return DFS(v[nod][i], count + 1);
	}
};
int main()
{
	citire();
	int x;
	x = BFS(1);
	for (int i = 0; i < 100000; i++)
		used[i] = 0;
	DFS(x, 1);
	printf("%d", max1);
	return 0;
}