Agora o algoritmo com o exemplo real.
Vamos acompanhar os dois casos de teste, observar a matriz, seguir a recursão e entender exatamente por que as respostas são 30 e 10.
Resumo do problema e da solução
Pedro quer desenhar um labirinto sem levantar a caneta do papel. Ele escolhe um nodo para começar, precisa passar por todas as linhas disponíveis do desenho e, no final, voltar para o mesmo nodo inicial.
O que precisamos descobrir?
Para cada caso de teste, recebemos o nodo inicial, a quantidade de vértices e as arestas do labirinto. A pergunta é: qual é o menor número de movimentos de caneta necessário para percorrer o desenho, saindo e terminando no mesmo ponto?
Por que DFS resolve?
Como o enunciado garante que não haverá ciclos, cada nova ligação descoberta pela DFS funciona como um caminho que Pedro precisa fazer na ida e repetir na volta. Por isso, a resposta é 2 × quantidade de arestas usadas para alcançar novos vértices.
Origem
O primeiro número de cada caso indica onde Pedro começa e onde deve terminar.
Labirinto
Os nodos são os vértices; os segmentos informados são as arestas disponíveis para desenhar.
Movimentos
Contamos quantas novas arestas a DFS usa e multiplicamos esse valor por 2.
Entrada e saída do exemplo
Entrada
Saída esperada
10
16 vértices · 15 arestas
Origem = 0. Todos os 16 vértices são alcançados pela DFS.
9 vértices · 6 linhas de aresta
Origem = 1. Apenas seis vértices são alcançados e uma ligação aparece repetida.
O algoritmo em uma frase
O programa monta uma matriz de adjacência e usa uma DFS recursiva para descobrir novos vértices a partir da origem.
Visitado?
-1 significa “ainda não visitei”. Qualquer outro valor significa visitado.
Ordem
Numera a ordem em que os vértices são descobertos pela DFS.
Descobertas
Incrementa apenas quando a DFS entra em um vértice ainda não visitado.
A DFS está aqui: pathR(v)
cnt += 1
pathR(w)
pathR(w) é o “vai fundo” da DFS.
Quando essa chamada termina, o C++ retorna automaticamente para a chamada do vértice anterior.
Os dois grafos do exemplo
O primeiro caso é praticamente uma árvore: 16 vértices, 15 arestas e todos alcançáveis a partir de 0.
No segundo caso, 0, 5 e 6 ficam isolados. Além disso, a aresta 1–4 aparece duas vezes na entrada.
Execução animada dos dois casos
Escolha o caso e acompanhe a ordem exata produzida pelo laço for (int w = 0; w < V; ++w).
O detalhe que explica o segundo resultado
No segundo caso aparecem estas duas linhas:
1 4 ... 4 1
adj[1][4] = 1 adj[4][1] = 1
1 4 já cria os dois sentidos.
Quando aparece 4 1, o programa apenas escreve 1 nas mesmas células novamente.
Não nasce uma nova ligação.
| Dado | Valor | Interpretação |
|---|---|---|
| A informado | 6 | Foram fornecidas 6 linhas de arestas. |
| Ligações distintas alcançáveis | 5 | 1–2, 1–4, 4–3, 4–7 e 7–8. |
| Vértices alcançados | 6 | 1, 2, 4, 3, 7 e 8. |
| movimentos | 5 | Uma descoberta para cada novo vértice após a origem. |
| Saída | 10 | 5 × 2. |
Por que as respostas são 30 e 10?
15 descobertas
A origem é 0. Existem 16 vértices alcançáveis. Depois do primeiro, cada novo vértice exige uma nova aresta da árvore DFS: 16 − 1 = 15.
5 descobertas
A partir de 1, somente 6 vértices são alcançados. Portanto a árvore DFS possui 6 − 1 = 5 arestas.
Código completo comentado
#include <iostream>
#include <vector>
int contador = 0;
std::vector<int> rotulo;
std::vector<std::vector<int>> adj;
void percorrer(int vertice) {
rotulo[vertice] = contador++;
std::cout << vertice << ' ';
for (int vizinho = 0;
vizinho < static_cast<int>(adj.size());
++vizinho) {
if (adj[vertice][vizinho] && rotulo[vizinho] == -1)
percorrer(vizinho);
}
}
int main() {
int vertices;
int arestas;
std::cin >> vertices >> arestas;
adj.assign(vertices, std::vector<int>(vertices, 0));
rotulo.assign(vertices, -1);
for (int i = 0; i < arestas; ++i) {
int a;
int b;
std::cin >> a >> b;
adj[a][b] = 1;
adj[b][a] = 1;
}
for (int v = 0; v < vertices; ++v)
if (rotulo[v] == -1)
percorrer(v);
}