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:
| //CAPCITY – SPOJ | |
| //Código por Sofhia de Souza Gonçalves | |
| #include <bits/stdc++.h> | |
| #define pb push_back | |
| using namespace std; | |
| const int maxn = 1e5+10; | |
| int n, m, vist[maxn], tempo, resp[maxn], comp[maxn]; //vist eh o vetor de visitados, tempo eh a variavel que guarda a quantidade | |
| //de componentes, resp eh o vetor que marca se a componente aponta ou nao pra outra, | |
| //e comp eh o vetor que guarda a componente de cada vertice. | |
| vector < int > grafo[maxn], grafo2[maxn], cont[maxn]; //grafo eh o grafo normal, grafo2 eh o grafo ao contrario e cont sao os vetores | |
| //dos vertices de cada componente. | |
| stack < int > pilha; //pilha para o algoritmo de scc | |
| void dfs(int u) | |
| { | |
| vist[u] = 1; //marco como visitado | |
| for(int v : grafo[u]) | |
| { | |
| if(!vist[v]) dfs(v); //chamo pros filhos nao visitados | |
| } | |
| pilha.push(u); //coloco na pilha depois de ter passado pelos filhos | |
| } | |
| void rdfs(int u) | |
| { | |
| comp[u] = tempo; //guardo o valor da componente de u | |
| cont[tempo].pb(u); //adiciono u ao vetor de vertices da componente dele | |
| for(int v : grafo2[u]) | |
| { | |
| if(!comp[v]) rdfs(v); //se os vizinhos nao foram visitados, chamo pra eles tambem | |
| } | |
| } | |
| void scc() | |
| { | |
| for(int i = 1 ; i <= n ; i++) | |
| { | |
| if(!vist[i]) dfs(i); //se o vertice ainda nao foi visitado, chamo a dfs | |
| } | |
| while(pilha.size()) //percorro a pilha | |
| { | |
| int u = pilha.top(); | |
| pilha.pop(); | |
| if(!comp[u]) //se a componente do vertice u ainda nao foi calculada, quer dizer que ele nao foi visitado ainda | |
| { | |
| tempo++; //aumento a quantidade de componentes | |
| rdfs(u); //chamo a dfs pro grafo contrario | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| cin >> n >> m; //leio o n e o m | |
| for(int i = 0 ; i < m ; i++) | |
| { | |
| int a, b; | |
| cin >> a >> b; | |
| grafo[a].pb(b); //monto o grafo | |
| grafo2[b].pb(a); //monto o grafo contrário | |
| } | |
| scc(); //calculo as componentes fortemente conexas | |
| memset(vist, 0, sizeof vist); //zero o vetor de visitados | |
| for(int i = 1 ; i <= n ; i++) | |
| { | |
| for(int v : grafo2[i]) //os v sao os vertices que apontam pra mim (pois estou verificando os do grafo contrario) | |
| { | |
| if(comp[i] != comp[v]) resp[comp[v]] = 1; //se a componente de i eh diferente da componente de v, quer dizer que a | |
| } //componente de v aponta para outra componente, entao marco resp[comp[v]] como 1 | |
| } | |
| int r, c = 0; | |
| for(int i = 1 ; i <= tempo ; i++) | |
| { | |
| if(!resp[i]) //se a componente i nao aponta pra nenhuma outra | |
| { | |
| r = i; //guardo qual a componente | |
| c++; //conto a quantidade de componentes que nao apontam pra nenhuma outra componente | |
| } | |
| } | |
| if(c != 1) //se nenhuma componente nao aponta pra outra ou se mais de 1 componente nao aponta, a resposta eh 0 | |
| { | |
| cout << "0\n"; | |
| return 0; | |
| } | |
| cout << cont[r].size() << "\n"; //imprimo o tamanho da componente | |
| sort(cont[r].begin(), cont[r].end()); //ordeno os vertices da componente | |
| for(int i = 0 ; i < cont[r].size() ; i++) | |
| { | |
| if(i != 0) cout << " "; | |
| cout << cont[r][i]; // imprimo os vertices | |
| } | |
| cout << "\n"; | |
| } |
