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
). - Pegar o vértice
mais distante de (é fácil notar que é uma folha) - Fazer uma DFS a partir de e achar o mais distante
- o diâmetro será a distância de ao mais distante.
Vamos ao código:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |