Official Analysis (C++)

Explanation

The trick here is to process the queries in reverse. That way, when we come across an append operation, we'll know all the replace operations that will come after.

Let's keep a hashmap $h$, where $h[x]$ is the number $x$ will get mapped to after all replace operations have completed.

For example, consider the third sample case and say we've only processed the last query In this case,

h = {2: 7}

However, after we've processed all the queries, our map will now be

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

If we hit an "append $x$" operation, we add $h[x]$ to the beginning of our array.

For the "replace $x$ with $y$" operation, it's a bit trickier:

• If $y$ isn't in $h$ yet, set $h[x]=y$.
• Otherwise, $h[x]=h[y]$, since $y$ won't be $x$'s final state after all operations.

And that's both types of queries handled!

Implementation

Time Complexity: $\mathcal{O}(q)$

Copy
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
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(" "))

Copy
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)))