Quebra-cabeça

quebra.cpp

// Quebra-Cabeça - F1P2 - OBI 2015
// Rogério Júnior
// Complexidade: O(n)

#include <cstdio>
#include <algorithm> // pair e make_pair

using namespace std;

#define MAXN 200200

pair<char,int> lista[MAXN]; // crio o vetor de pares de char e int de nome "lista"

int n, prox; // declaro os inteiros "n" e "prox"

int main(){
	
	scanf("%d", &n); // leio a quantidade de peças
	
	for(int i=1; i<=n; i++){ // para cada peça do quebra-cabeça
		
		// declaro e leio seus valores de "e", "d" e "c"
		int e, d;
		char c;
		scanf(" %d %c %d", &e, &c, &d);
		
		// e adiciono essa peça ao vetor "lista"
		lista[e]=make_pair(c, d);
	}
	
	// agora basta montar o quebra-cabeça
	// que continuará enquanto o número da parte direita da peça atual não for 1
	while(prox!=1){ // prox será o número da parte esquerda da peça que irei imprimir
		
		printf("%c", lista[prox].first); // imprimo o caractere dessa peça
		
		// e faço a próxima peça a ser acessada ser a do número direito da peça atual
		prox=lista[prox].second;
	}
	
	// no fim da saída, imprimo a quebra de linha
	printf("\n");
	
	return 0;
}