Solução Desafio Cartográfico

Este é um tipo de problema clássico: achar o diâmetro da uma árvore. Há duas versões diferentes para o problema: caso o grafo tenha peso nas arestas e caso não tenha. A primeira é consideravelmente mais fácil que a segunda, e é o caso do problema.

Para resolver o problema, fazemos os seguintes passos:

  • Fazer uma DFS ou BFS em um vértice qualquer (digamos, o 1).
  • Pegar o vértice v mais distante de 1 (é fácil notar que é uma folha)
  • Fazer uma DFS a partir de v e achar o mais distante
  • o diâmetro será a distância de v ao mais distante.

Vamos ao código:


#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define MAXN 1000010
//Globais------------------------------
int n;
vector <int> mapa[MAXN];
bool marcado[MAXN];
int maior_distancia, vertice_distante; //auxiliares da dfs "especial"
//-------------------------------------
int liga(int x, int y){
mapa[x].push_back(y);
mapa[y].push_back(x);
}
int dfs(int v, int distancia){
marcado[v]=1;
if(distancia > maior_distancia){
maior_distancia=distancia;
vertice_distante=v;
}
int nv=mapa[v].size(); //determino número de vizinhos de "v"
for(int i=0;i<nv;i++){
if( !marcado[ mapa[v][i] ] )
dfs(mapa[v][i], distancia+1);
}
}
int main(){
int x,y;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
liga(x,y);
}
for(int i=1;i<=n;i++) marcado[i]=0;
dfs(1,0);
for(int i=1;i<=n;i++) marcado[i]=0;
dfs(vertice_distante,0);
printf("%d\n", maior_distancia);
return 0;
}