Pagini recente » Cod sursa (job #994073) | Cod sursa (job #1711837) | Atasamentele paginii oli.2009.simulare | Cod sursa (job #1979668) | Cod sursa (job #1731875)
#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;
}