Cod sursa(job #1731875)

Utilizator serbanmaria15Serban Maria-Catalina serbanmaria15 Data 20 iulie 2016 12:00:59
Problema Diametrul unui arbore Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#define N_MAX 100001

std::vector<int> adiacenta[N_MAX];
std::queue<int> coada;
int n, lungDrum[N_MAX], viz[N_MAX], ultim, diametru;

void bfs(int nodPlecare)
{
	int i, nodCurent;
	memset(lungDrum, 0, N_MAX);//initializare vector lungDrum cu 0
	memset(viz, 0, N_MAX);//initializare vector viz cu 0

	coada.push(nodPlecare);//punem nodul de plecare in coada
	lungDrum[nodPlecare]=1;
	viz[nodPlecare]=1;
	while(!coada.empty())
	{
		nodCurent=coada.front();
		for(i=0; i<adiacenta[nodCurent].size(); i++)
		{
			if(viz[adiacenta[nodCurent][i]]==0)
			{
				coada.push(adiacenta[nodCurent][i]);
				lungDrum[adiacenta[nodCurent][i]]=lungDrum[nodCurent]+1;
				viz[adiacenta[nodCurent][i]]=1;

				diametru=lungDrum[adiacenta[nodCurent][i]];
				ultim=adiacenta[nodCurent][i];
			}
		}
		coada.pop();
	}
}

int main()
{
	FILE *inputFile, *outputFile;
	inputFile=fopen("darb.in", "r");
	outputFile=fopen("darb.out", "w");

	int i, a, b;
	fscanf(inputFile, "%d", &n);
	for(i=0; i<n-1; i++)//merge pana la n-1 pt ca arborele are nr de muchii=nrNoduri-1
	{
		fscanf(inputFile, "%d %d", &a, &b);
		//actualizam adiacentele
		adiacenta[a].push_back(b);
		adiacenta[b].push_back(a);
	}

	bfs(1);
	bfs(ultim);
	fprintf(outputFile, "%d", diametru);

	return 0;
}