Preso no Castelo

castelo.cpp

#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;
}