Cod sursa(job #1228170)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 12 septembrie 2014 22:15:23
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 100001

vector <int> v[NMAX];
int lev[NMAX],d[NMAX];

void dfs(int nod, int tata)
{
	int frunza;
	frunza=1;
	for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
		if(*it!=tata) {
			dfs(*it,nod);
			frunza=0;
			lev[nod]=max(lev[nod],lev[*it]+1);
		}
	if(frunza) {
		lev[nod]=1;
		d[nod]=1;
	}
	else {
		d[nod]=lev[nod];
		int max1,max2;
		max1=max2=0;
		for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++) {
			if(*it==tata)
				continue;
			if(lev[*it]>=max1) {
				max2=max1;
				max1=lev[*it];
			}
			else if(lev[*it]>max2)
				max2=lev[*it];
		}
		if(max1 && max2)
			d[nod]=max(d[nod],max1+max2+1);
	}
}

int main ()
{
	int n,x,y,i,sol;
	ifstream f("darb.in");
	ofstream g("darb.out");
	f>>n;
	for(i=1;i<=n-1;i++) {
		f>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	f.close();
	dfs(1,0);
	sol=0;
	for(i=1;i<=n;i++)
		sol=max(sol,d[i]);
	g<<sol;
	g.close();
	return 0;
}