Solução por Sofhia de Souza
Esse problema trata-se de um problema de Componentes Fortemente Conexas (nessa solução, iremos usar o Algoritmo de Kosaraju). É recomendado que o leitor já tenha conhecimento do algoritmo.
Trataremos o país como um grafo, e as cidades como os vértices do grafo. Analisando bem, notaremos que as cidades que são acessíveis por todas as outras cidades são aquelas que pertencem a uma mesma componente fortemente conexa (pois elas devem chegar de uma as outras), e essa componente deve ser acessada por todas as outras componentes do grafo. Em outras palavras, devemos encontrar a única componente fortemente conexa do grafo que não acessa nenhuma outra componente (caso existam mais de uma ou nenhuma, a resposta será 0). Para fazermos isso, iremos primeiro calcular as componentes fortemente conexas utilizando o algoritmo de Kosaraju, e com ele iremos guardar todos os vértices pertencentes a cada componente. Depois disso, marcaremos para cada componente se ela acessa ou não alguma outra componente (para isso, basta verificarmos os vizinhos de cada vértice e vermos se eles são ou não parte de uma mesma componente). Por fim, verificaremos se existe apenas uma componente que não aponta para nenhuma outra. Se sim, imprimimos seu tamanho e os vértices que fazem parte dela, de forma ordenada. Segue o código para melhor entendimento:
https://gist.github.com/sofhiasouza/c2f7a24c3130a2a1e96647883a47dd97