Find and Replace (USACO Silver 2023 January)

贪心思路：

如果同一个字符在输出字符串中变成了不同的字符，输出 $-1$ 。
对于 $(\text{input}, \text{output})$ 对进行去重。
如果存在 $\text{input} \neq \text{output}$ ，且不同的 $\text{output}$ 字符数量达到 $52$ ，则输出 $-1$ 。（这一步是简化后面问题的关键，要想到有一定难度）
如果存在替换环（例如 $A \to B, B \to C, C \to A$ ），需要通过将环中的某个字母先变成一个未出现过的新字母来打破环，分两种情况：
1. 如果环中存在某个字母 $x$ 的入度大于 $1$ （即有环外的字母指向 $x$ ），只需将环中 $x$ 前面的字母变成该入度对应的字母，答案不变。
2. 否则，先将环中任意一个字母变成一个未用过的字母，答案加 $1$ 。
如果所有可能的字符对（ $52 \times 52$ ）都被用完且存在环，输出 $-1$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
char s1[100005], s2[100005];
int mp[255];
set<pair<int,int>> st;
set<int> ts;   // all t values
 
void solve() {
    memset(mp,0,sizeof(mp));
    st.clear();
    ts.clear();
    int L = strlen(s1);
    for (int i = 0; i < L; i++) {
        char c1 = s1[i], c2 = s2[i];
        if (mp[c1] != 0 && mp[c1] != c2) {
            printf("-1\n");
            return;
        }
        mp[c1] = c2;
        if (c1 != c2) st.insert({c1,c2});
        ts.insert(c2);
    }
    int ans = st.size();
    bool seen[255] = {0};
    int in_deg[255] = {0};
    for (auto p : st) in_deg[p.s]++;
    for (auto p : st) {
        // tortoise and hare to find loops
        int x = p.s, y = mp[p.s];
        while (x != y && !seen[x] && y != 0) {
            seen[x] = true;
            x = mp[x];
            y = mp[mp[y]];
        }
        if (x == y && mp[x] != x) {            // not a self loop
            seen[x] = true;
            bool found = in_deg[y] > 1;        // find a letter with in-degree > 1
            int cnt = 1;
            for (y = mp[y]; y != x; y = mp[y]) {
                seen[y] = true; // mark the loop as visited
                if (in_deg[y] > 1)
                    found = true;
                cnt++;
            }
            // printf("cnt: %d\n",cnt);
            if (!found) {
                if (ts.size() == 52) {             // out of letter to break the loop
                    printf("-1\n");
                    return;
                } else
                    ans++;
            } else {
                // nothing, break the loop through the in-degree >0 letter
            }
        }
    }
    printf("%d\n",ans);
}
 
int main() {
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s %s",s1,s2);
        solve();
    }
    return 0;
}