Solução escrita por Malu Azevedo
Conhecimentos necessários:
O problema nos pede para determinar, para cada uma das rotas planejadas (sequências de ilhas), quantas viagens de avião Guilherme precisará fazer, sabendo que um voo é necessário apenas entre duas ilhas consecutivas na rota que não estejam conectadas por nenhuma estrada (ou seja, que pertençam a componentes conexas diferentes).
Ideia Central
A ideia central para resolver o problema é reconhecer que as ilhas conectadas direta ou indiretamente por estradas formam agrupamentos conhecidos em teoria de grafos como componentes conexas. Duas ilhas podem ser visitadas por carro ou ônibus sem a necessidade de pegar um avião se, e somente se, elas estiverem na mesma componente conexa. Assim, podemos modelar o arquipélago como um grafo não direcionado, onde as ilhas são os vértices e as estradas são as arestas. Utilizando um algoritmo de busca, como a Busca em Largura (BFS), podemos percorrer o grafo para identificar e rotular cada ilha com o identificador da sua respectiva componente conexa. Dessa forma, para cada rota de viagem, basta percorrermos a sequência de ilhas consecutivas e verificar se o par de ilhas adjacentes possui o mesmo identificador de componente, caso contrário, um voo é contabilizado.
Abordagem completa
Lemos os valores de n e m e construímos a lista de adjacência do grafo com as estradas fornecidas. Em seguida, utilizamos um vetor de visitados (visited) e um loop de 1 até n para disparar buscas em largura (BFS) em todas as ilhas ainda não visitadas, atribuindo um identificador numérico único (nc) para todas as ilhas alcançáveis a partir de cada raiz. Após processar o grafo em tempo linear, lemos a quantidade de rotas q e, para cada rota composta por k ilhas, iteramos sobre os pares consecutivos para acumular um contador de voos sempre que os identificadores de componentes forem diferentes (comp[rotas[i]] != comp[rotas[i+1]]). Ao final de cada rota, imprimimos o total de voos necessários.