Imperialismo - Pedro Michael

imperialismo_pedro.cpp

#include <stdio.h>
#include <vector>
#include <string.h>
#define MAX 100001
using namespace std;

vector<int> grafo[MAX];

int vis[MAX], v, d;

void dfs(int u, int dist)
{
	vis[u]=1;
	
	// se encontrei o mais distante, atualizo
	if(dist > d)
		d = dist, v = u;
	
	// para cada vizinho de u
	for(int i = 0; i < grafo[u].size(); i++)
	{	
		
		// chamo a DFS nos ainda não explorados
		int no = grafo[u][i];
		if(!vis[no])
			dfs(no, dist+1);
	}
}
int main()
{
	int n, pi;
	while(scanf("%d", &n) && n != -1)
	{
		for(int i = 1; i <= n; i++)
			vis[i] = 0, grafo[i].clear();
		
		// leio o grafo
		for(int i = 2; i <= n; i++)
		{
			scanf("%d", &pi);
			grafo[pi].push_back(i);
			grafo[i].push_back(pi);
		}
		
		// através de DFS em árvores
		
		// encontro o vizinho mais distante de 1, v
		d=0;
		dfs(1, 0);
		for(int i = 1; i <= n; i++)
			vis[i] = 0;
		
		// e a distância para o vizinho mais distante de v
		d=0;
		dfs(v, 0);
		
		// e imprimo a resposta
		printf("%d\n", (d+1) / 2);
	}
	return 0;
}