Submission #73819125

---

Source Code Expand

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

#define int long long

const int inf = 1e18;
const int mod  = 1e9 + 7;

void solve(){
    int n, m; cin >> n >> m;

    vector<string> s(n);
    for(auto &i: s) cin >> i;

    vector<int> chan(26, -1);

    for(int i = 0; i < m; i++){
        char x, y; cin >> x >> y;
        chan[x - 'a'] = y - 'a';
    }

    vector<int> vis(26, 0);

    auto help = [&](int ch, auto &&self) -> int {

        if(chan[ch] == -1) return ch;

        if(vis[ch]) return ch; // cycle protection

        vis[ch] = 1;
        int res = self(chan[ch], self);
        vis[ch] = 0;

        return chan[ch] = res;
    };

    for(int i = 0; i < 26; i++){
        if(chan[i] != -1){
            chan[i] = help(i, help);
        }
    }

    for(auto &st: s){
        for(auto &c: st){
            int x = c - 'a';
            cout << char(chan[x] == -1 ? x + 'a' : chan[x] + 'a');
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Submission Info

Judge Result