Solução por Rogério Júnior
Este problema é feito usando-se uma única BFS, com um apequena modificação. Se você não sabe o que é BFS, clique aqui para ver a aula do Curso Noic sobre algoritmos de Flood Fill. Para começarmos o problema, vamos ler a entrada, salvando as chaves no array de vectors de nome key (key[i] é um vetor com os números das salas que pode ser aberta com as chaves encontradas na sala i) e o grafo em uma lista de adjacências, o array de vectors de int de nome lista. Basta agora implementarmos a BFS modificada que irá retornar true caso possamos visitar todas as salas do castelo e false, caso contrário.
Além do vetor marcado que guardará as salas não visitadas, teremos o vetor forb que guardará as salas que ainda não podemos visitar po não termos a chave (se forb[i]==true, não tenho a chave da sala i). Para iniciarmos o loop da BFS, salvamos que não temos nenhuma chave exceto a da sala 1, a marcamos como visitada e a colocamos na fila da BFS. Agora, como no algoritmo comum, salvo a próxima sala da fila em um inteiro davez e a tiro da fila. Se eu não tiver sua chave, devo reinseri-la no final da fila, pois pode ser que encontremos sua chave posteriormente, e só então poderemos abri-la, logo, não devemos tirá-la da fila de salas acessíveis. Se eu já tiver a chave de davez, executo normalmente a BFS, adicionando seus vizinhos não marcados à fila e guardando, em marcado, que já foram visitados, lembrando apenas de olhar as chaves encontradas nessa sala (no vector key[davez]) e salvar que são todas acessíveis, usando um for para marcar false em suas respectivas posições do vetor forb.
Entretanto, se não for possível que visitemos todas as salas, o programa descrito até aqui poderá entrar em loop infinito. Note que que se é impossível chegar a uma sala porque não tenho sua chave, ela nunca sairá da fila (pois sempre a reinsiro essa sala no final da fila) e o loop nunca acaba. Portanto, só preciso continuar a BFS enquanto houver salas na fila que posso visitar (já tenho a chave), pois se ficarem apenas salas inacessíveis, devo será impossível abri-las e a BFS deve retornar false.
Note que, se houver apenas salas inacessíveis na fila, a BFS irá percorrer todas, uma a ma, retirando e reinserindo-as na fila. Caso isso ocorra, ela deve retornar false. Para identificarmos se isso ocorreu, basta que, sempre que reinserirmos alguém na fila, salvarmos qual sala foi a primeira a ser reinserida em uma variável first. Assim , se a BFS continuar, percorrer toda a fila, e o primeiro voltar a ser o primeiro elemento reinserido, devemos retornar false. No entanto, se encontrarmos uma única sala que podemos acessar (que já temos a chave), então não precisaremos fazer essa checagem (pois ela busca saber se todas as salas da fila são inacessíveis) e reiniciamos o valor de first para zero, pois não há salas com esse número. Note que para sempre mantermos a primeira sala que é inacessível em first, basta que só a atualizemos se ela estiver com seu valor inicial zero.
Terminado o loop da BFS, basta verificar se todas as salas foram visitadas. Para isso basta salvarmos uma variável count, de valor inicial zero, e adicionarmos uma unidade a seu valor sempre que visitamos uma sala nova. No fim da BFS, retornamos true se o número de salas visitadas count for igual ao número de salas n, retornando false caso contrário. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cstring> | |
#include <vector> | |
#include <queue> | |
#define MAXN 1010 | |
using namespace std; | |
vector<int> lista[MAXN]; | |
vector<int> key[MAXN]; | |
bool forb[MAXN], marcado[MAXN]; | |
int n, m; | |
// BFS modificada | |
bool bfs(){ | |
queue<int> fila; | |
fila.push(1); | |
memset(forb, true, sizeof(forb)); | |
memset(marcado, false, sizeof(marcado)); | |
forb[1]=false; | |
marcado[1]=true; | |
int davez, tam, count=0,first=0; | |
// loop principal | |
while(!fila.empty()){ | |
// salvo a primeira sala da fila e a retiro dela | |
davez=fila.front(); fila.pop(); | |
// se ainda não tenho a sua chave | |
if(forb[davez]){ | |
// verifico se a BFS não acabou de percorrer todas as salas da fila | |
// e nenhuma delas era acessível. Se isso ocorrer, a BFS retorna false | |
if(davez==first) return false; | |
// caso contrário, reinsiro a sala no fim da fila | |
fila.push(davez); | |
// e se ela for a primeira sala de uma sequência a ser reinserida | |
// salvo seu número em first | |
if(!first) first=davez; | |
// e continuo para a próxima repetição do for | |
continue; | |
} | |
// se posso acessar a sala, então first recebe zero | |
// pois achei uma sala na fila que é acssível | |
first=0; | |
// aumento o número de salas que posso visitar | |
count++; | |
// e olho todas as chaves encontradas na sala, | |
// salvando, com false em forb, que elas são agora acessíveis | |
tam=key[davez].size(); | |
for(int i=0; i<tam; i++) forb[key[davez][i]]=false; | |
// e como em uma BFS normal, procuro por vizinhos ainda não visitados | |
// os marco e adiciono na fila | |
tam=lista[davez].size(); | |
for(int i=0; i<tam; i++) if(!marcado[lista[davez][i]]){ | |
fila.push(lista[davez][i]); | |
marcado[lista[davez][i]]=true; | |
} | |
} | |
// por fim, se tiver visitado todas as salas, a BFS retorna true | |
return count==n; | |
} | |
int main(){ | |
// processo todos os casos de entrada até fim de arquivo | |
while(scanf("%d %d", &n, &m)!=EOF){ | |
// reinicio os arrays do programa | |
for(int i=0; i<=n; i++){ | |
lista[i].clear(); | |
key[i].clear(); | |
} | |
// leio o grafo e o salvo na lista de adjacências | |
int a, b; | |
for(int i=0; i<m; i++){ | |
scanf("%d %d", &a, &b); | |
lista[a].push_back(b); | |
lista[b].push_back(a); | |
} | |
// depois leio onde está a chave da cada sala | |
for(int i=2; i<=n; i++) { | |
scanf("%d", &a); | |
key[a].push_back(i); | |
} | |
// por fim, se a bfs retornar true, então posso visitar todas as salas | |
if(bfs()) printf("sim\n"); | |
// caso contrário, não posso | |
else printf("nao\n"); | |
} | |
return 0; | |
} |