pontes.cpp

#include <cstdio> // scanf e printf
#include <cstring> // memset

#define MAXR 110 // número máximo de regiões
#define MAXK 10100 // número máximo de pontes

int r, k, inc[110], tab[110][10100]; // declaração de variáveis

bool controle;

bool possivel(int davez, int qtd){ // função recursiva da dp
	
	// se já achei uma solução, então pronto, retorne a função
	if(controle==true) return true;
	
	// se a função já foi calculada para estes parâmetros, retorne o valor que temos salvo
	if(tab[davez][qtd]>=0) return tab[davez][qtd];
	
	// se davez>r, já testamos todas as regiões e ainda não encontramos um jeito, retorne false
	if(davez>r) return tab[davez][qtd]=false;
	
	// se qtd=k, então acabamos de achar um conjunto que é exemplo do que o problema pede, retorne true
	if(qtd==k) return tab[davez][qtd]=controle=true;
	
	// se qtd>k, já estouramos a cota de pontes e esse conjunto irá atingir mais que k pontes
	if(qtd>k) return tab[davez][qtd]=false;
	
	// chamamos a recursão: vemos se é possível ter k pontes colocando ou não a próxima região
	if(possivel(davez+1, qtd+inc[davez+1]) || possivel(davez+1, qtd)) return tab[davez][qtd]=controle=true;
	
	// se o programa chegou aqui, então o "if" de cima não retornou e não foi possível achar as k pontes
	return tab[davez][qtd]=false;
}

// perceba como a função sempre atualiza os valores salvos na tabela de pd e na variável controle

int main(){
	
	while(scanf("%d %d", &r, &k)!=EOF){ // lemos os vários casos de teste da entrada
		
		memset(inc, 0, sizeof(inc)); // zeramos o número de pontes que incide em cada região
		
		memset(tab, -1, sizeof(tab)); // colocamos -1 em todos os valores da tabela de pd
		
		controle=false; // dizemos que ainda não encontramos solução
		
		int r1, r2;
		
		for(int i=0; i<k; i++){
		
			scanf("%d %d", &r1, &r2); // lemos as pontes da entrada
			
			// e adicionamos 1 unidade na incidência de pontes das cidades nas duas extremiades da ponte
			inc[r1]++;
			inc[r2]++;
		}
		
		// se a função retornar true, imprimimos 'S', caso contrário, imprimimos 'N'
		printf("%c\n", possivel(0, 0) ? 'S':'N');
		
	}
	
	return 0;
}