Por essa eu não esperava. Aparentemente o enunciado está errado mesmo, e o grafo dado pode ser desconexo.
Adaptem o algoritmo para que funcione da maneira sugerida pelo Hugo.
Forum