Inp : 10 1 c 1 b 1 a 1 c 1 d 2 a b 1 c 1 a 1 b 2 b d Out : cddcdcad

Thuật toán

Thay vì mình xử lý từng thao tác theo thứ tự, ta sẽ đi xử lý các thao tác theo thứ tự ngược lại.

Khi ta xử lý từng thao tác, ta sẽ giữ một mảng lưu các ký tự được biến đổi và chữ cái cuối cùng nó trở thành sau mọi phép biến đổi. Ta sẽ giữ mảng này bằng một map hoặc unordered_map tên là mp.

Ta sẽ xử lý mỗi thao tác theo thứ tự như đã nói như sau:

- $1$ $x$: Thêm chữ cái $mp_x$ vào đầu xâu đáp án. Ta có thể thêm vào cuối xâu, sau tất cả các thao tác ta sẽ đảo ngược xâu kết quả lại.

- $2$ $x$ $y$: Thay đổi $mp_x = mp_y$, do chữ cái $x$ biến đổi thành chữ cái $y$, và cuối cùng chữ cái $y$ sau các thao tác cuối cùng sẽ thành chữ cái $mp_y$.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int n,tp;
char x,y,c;
vector<pair<bool, string>> all;
map<char, char> mp;
string s,ans;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> tp;
        s = "";
        if(tp == 1){
            cin >> x;
            s += x;
            all.push_back(make_pair(false,s));
        }else{
            cin >> x >> y;
            s += x; s += y;
            all.push_back(make_pair(true, s));
        }
    }
    reverse(all.begin(),all.end());
    for(char c='a';c<='z';c++) mp[c] = c;
    ans = "";
    for(pair<bool, string> item: all){
        if(item.first){
            mp[item.second[0]] = mp[item.second[1]];
        }else{
            c = mp[item.second[0]];
            while(mp[c] != c) c = mp[c];
            ans += c;
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans;
    return 0;
}