Cod sursa(job #1145571)

Utilizator anaid96Nasue Diana anaid96 Data 18 martie 2014 12:02:16
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

FILE *in,*out;

//constante
const int Nmax = (int) 1e5+1;
const int oo = 0x3f3f3f3f;

//definitii
#define pb push_back


//functii
void bfs(int node);

//variabile
int n,nod1,nod2;
vector<int> graf[Nmax];
int first=1,last;
int dist;
int distanta[Nmax];

int main(void)
{
	in = fopen("darb.in" , "rt");
	out = fopen("darb.out" , "wt");
	
	fscanf(in,"%d", &n);
	
	for(int i=1 ; i<n ; ++i)
	{
		fscanf(in, "%d%d",&nod1,&nod2);
		graf[nod1].pb(nod2);
		graf[nod2].pb(nod1);		
	}
	
	bfs(first);
	bfs(last);
	
	fprintf(out,"%d\n",dist+1);
	
	fclose(in);
	fclose(out);
	return 0;
	
}

void bfs(int node)
{
	queue<int> q;
	q.push(node);
	memset(distanta,oo,sizeof(distanta));
	distanta[node]=0;
	dist=0;
	
	while(!q.empty())
	{
		int curent = q.front();
		q.pop();
		
		vector<int> :: iterator it,end=graf[curent].end();
		for(it=graf[curent].begin() ; it!=end ; ++it)
		{
			if(distanta[*it]==oo)
			{
				q.push(*it);
				distanta[*it]=distanta[curent]+1;
				if(dist<distanta[*it])
				{
					dist=distanta[*it];
					last=*it;
				}
			}
		}
		
	}
	
}