Replace the Numbers (Codeforces 1620E)
Tags: Others, dsu

You have an array of integers (initially empty).You have to perform $$$q$$$ queries. Each query is of one of two types:   "$$$1$$$ $$$x$$$" — add the element $$$x$$$ to the end of the array;  "$$$2$$$ $$$x$$$ $$$y$$$" — replace all occurrences of $$$x$$$ in the array with $$$y$$$. Find the resulting array after performing all the queries.

Input: The first line contains a single integer $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — the number of queries.Next $$$q$$$ lines contain queries (one per line). Each query is of one of two types:   "$$$1$$$ $$$x$$$" ($$$1 \le x \le 5 \cdot 10^5$$$);  "$$$2$$$ $$$x$$$ $$$y$$$" ($$$1 \le x, y \le 5 \cdot 10^5$$$). It's guaranteed that there is at least one query of the first type.

Output: In a single line, print $$$k$$$ integers — the resulting array after performing all the queries, where $$$k$$$ is the number of queries of the first type.

Note: In the first example, the array changes as follows:$$$[]$$$ $$$\rightarrow$$$ $$$[3]$$$ $$$\rightarrow$$$ $$$[3, 1]$$$ $$$\rightarrow$$$ $$$[3, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 3, 2]$$$.In the second example, the array changes as follows:$$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 2]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$.In the third example, the array changes as follows:$$$[]$$$ $$$\rightarrow$$$ $$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 4]$$$ $$$\rightarrow$$$ $$$[1, 4, 2]$$$ $$$\rightarrow$$$ $$$[1, 4, 4]$$$ $$$\rightarrow$$$ $$$[1, 3, 3]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 2]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 7]$$$.

Sample Inputs:
7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3

4
1 1
1 2
1 1
2 2 2

8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7

Sample Outputs:
3 2 2 3 2

1 2 1

1 3 3 7

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def replace_the_number(q, queries):
    output = []
    transformations = {}
    for i in range(q - 1, -1, -1):
        query = queries[i]
        if query[0] == '1':
            value = int(query[2:])
            value = transformations.get(value, value)
            output += [value]
        else:
            (x, y) = map(int, query[2:].split())
            if y in transformations:
                transformations[x] = transformations[y]
            else:
                transformations[x] = y
    output = output[::-1]
    return ' '.join(map(str, output))
q = int(input())
queries = [None] * q
for i in range(q):
    queries[i] = input().decode()
sys.stdout.write(f'{replace_the_number(q, queries)}\n')

Solution (Python):
import sys
input = lambda : sys.stdin.readline()[:-1]

def replace_the_number(q, queries):
    output = []
    transformations = {}
    for i in range(q - 1, -1, -1):
        query = queries[i]
        if query[0] == '1':
            value = int(query[2:])
            value = transformations.get(value, value)
            output += [value]
        else:
            (x, y) = map(int, query[2:].split())
            if y in transformations:
                transformations[x] = transformations[y]
            else:
                transformations[x] = y
    output = output[::-1]
    return ' '.join(map(str, output))
q = int(input())
queries = [None] * q
for i in range(q):
    queries[i] = input()
sys.stdout.write(f'{replace_the_number(q, queries)}\n')

Solution (Python):
replaces = {}
q = int(input())
requests = [input() for i in range(q)]
ans = []
for r in requests[::-1]:
    if r[0] == '1':
        v = int(r[2:])
        ans.append(replaces.get(v, v))
    else:
        (u, w) = map(int, r[2:].split())
        replaces[u] = replaces.get(w, w)
print(*ans[::-1])