Solução de Pedro Michael, comentários de Rogério Júnior
Para ver o problema original, clique aqui.
Observe o pior caso possível: uma a uma, todas as cidades do maior caminho do grafo são conquistadas por uma das cidades das pontas. Neste caso, se o maior caminho tivesse tamanho $$d$$, ele demoraria exatamente $$\big\lceil\frac{d}{2}\big\rceil$$ anos para ser totalmente conquistado. Desse modo, basta descobrirmos o tamanho $$d$$ do maior caminho numa árvore (seu diâmetro) e imprimirmos o valor de $$\big\lceil\frac{d}{2}\big\rceil$$.
Para descobrir o diâmetro de um árvore, escolhemos um vértice qualquer $$v_ori$$ e encontramos seu vizinho mias distante $$v_1$$. Depois, encontramos o vértice $$v_2$$, vizinho mais distante de $$v_1$$, e o caminho de $$v_1$$ a $$v_2$$ é um diâmetro, e tem comprimento $$d$$ máximo.
Segue o código para melhor entendimento:
This file contains hidden or 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 <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; | |
| } |
Comente