Cod sursa(job #1094747)

Utilizator fhandreiAndrei Hareza fhandrei Data 29 ianuarie 2014 19:54:47
Problema Diametrul unui arbore Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
// Include
#include <fstream>
#include <vector>
using namespace std;

// Definitii
#define pb push_back

// Constante
const int sz = (int)1e5+1;

// Functii
void mainDFS(int node, int father);
void lengthDFS(int node, int father, int level);

// Variabile
ifstream in("darb.in");
ofstream out("darb.out");

int nodes;

vector<int> graph[sz];

int answer;

// Main
int main()
{
    in >> nodes;
	
	int rFrom, rTo;
	for(int i=1 ; i<nodes ; ++i)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	
	mainDFS(1, -1);
	
	out << answer << '\n';
	
	in.close();
	out.close();
	return 0;
}

void mainDFS(int node, int father)
{	
	if(graph[node].size() == 1)
		lengthDFS(node, -1, 1);
	
	vector<int>::iterator it, end=graph[node].end();
	for(it=graph[node].begin() ; it!=end ; ++it)
		if(*it != father)
			mainDFS(*it, node);
}

void lengthDFS(int node, int father, int level)
{
	answer = max(answer, level);
	
	vector<int>::iterator it, end=graph[node].end();
	for(it=graph[node].begin() ; it!=end ; ++it)
		if(*it != father)
			lengthDFS(*it, node, level+1);
}