Skip to Content
CTRL K

Replace the Numbers

Análisis oficial (C++) 

Explicación

El truco aquí es procesar las consultas en reversa. Así, cuando nos encontramos con una operación de agregar, conoceremos todas las operaciones de reemplazo que vendrán después.

Mantengamos una tabla hash hh, donde h[x]h[x] es el número al que se mapeará xx después de que se hayan completado todas las operaciones de reemplazo.

Por ejemplo, consideremos el tercer caso de ejemplo y digamos que solo hemos procesado la última consulta. En este caso,

h = {2: 7}

Sin embargo, después de haber procesado todas las consultas, nuestro mapa será

h = {1: 3, 2: 3, 4: 3}

Si nos encontramos con una operación “agregar xx”, agregamos h[x]h[x] al comienzo de nuestro arreglo.

Para la operación “reemplazar xx por yy”, es un poco más complicado:

  • Si yy aún no está en hh, asignamos h[x]=yh[x]=y.
  • En caso contrario, h[x]=h[y]h[x]=h[y], ya que yy no será el estado final de xx después de todas las operaciones.

¡Y con eso están cubiertos ambos tipos de consultas!

Implementación

Complejidad temporal: O(q)\mathcal{O}(q)

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int query_num;
	std::cin >> query_num;
	vector<vector<int>> queries;
	for (int q = 0; q < query_num; q++) {
		int type;
		std::cin >> type;
		if (type == 1) {
			int elem;
			std::cin >> elem;
			queries.push_back({type, elem});
		} else if (type == 2) {
			int x, y;
			std::cin >> x >> y;
			queries.push_back({type, x, y});
		}
	}
 
	std::map<int, int> mappings;
	vector<int> arr;
	std::reverse(queries.begin(), queries.end());
	for (const vector<int> &q : queries) {
		if (q[0] == 1) {
			arr.push_back(mappings.count(q[1]) ? mappings[q[1]] : q[1]);
		} else if (q[0] == 2) {
			mappings[q[1]] = mappings.count(q[2]) ? mappings[q[2]] : q[2];
		}
	}
 
	for (int i = arr.size() - 1; i >= 0; i--) { cout << arr[i] << " \n"[i == 0]; }
}
import java.io.*;
import java.util.*;
 
public class ReplaceTheNumbers {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(read.readLine());
		int[][] queries = new int[queryNum][];
		for (int q = 0; q < queryNum; q++) {
			queries[q] = Arrays.stream(read.readLine().split(" "))
			                 .mapToInt(Integer::parseInt)
			                 .toArray();
		}
 
		Map<Integer, Integer> mappings = new HashMap<>();
		List<Integer> arr = new ArrayList<>();
		for (int q = queryNum - 1; q >= 0; q--) {
			if (queries[q][0] == 1) {
				arr.add(mappings.getOrDefault(queries[q][1], queries[q][1]));
			} else if (queries[q][0] == 2) {
				int x = queries[q][1], y = queries[q][2];
				mappings.put(x, mappings.getOrDefault(y, y));
			}
		}
 
		for (int i = arr.size() - 1; i >= 0; i--) {
			System.out.print(arr.get(i) + (i == 0 ? "\n" : " "));
		}
	}
}
queries = []
for _ in range(int(input())):
	queries.append(tuple(int(i) for i in input().split()))
 
mappings = {}
arr = []
for q in reversed(queries):
	if q[0] == 1:
		arr.append(mappings.get(q[1], q[1]))
	elif q[0] == 2:
		mappings[q[1]] = mappings.get(q[2], q[2])
 
print(" ".join(str(i) for i in reversed(arr)))
Fundamentos