并查集模板题。

解题思路

• 把字符串的每个位置看作一个节点，可交换位置对看作一条无向边。
• 遍历所有根节点，检查每个分量中 $S$ 和 $T$ 的字符计数是否完全一致。
• 若所有分量都一致，输出 Yes 否则输出 No。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int f[maxn],n,m,s[maxn][26],t[maxn][26];
char a[maxn],b[maxn];
// 并查集查找
int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
int main()
{
    cin>>n>>m>>a>>b;
    //初始化
    for(int i=1;i<=n;++i) f[i]=i;
    //合并可交换的位置
    for(int i=0;i<m;++i)
    {
        int x,y;
        cin>>x>>y;
        x=find(x);
        y=find(y);
        if(x!=y) f[y]=x;
    }
    //统计每个连通分量内 a、b 字符串的字符数量
    for(int i=1;i<=n;++i)
    {
        int r=find(i);
        s[r][a[i-1]-'a']++;
        t[r][b[i-1]-'a']++;
    }
    //检查每个字符是否匹配
    for(int i=1;i<=n;++i)
    {
        if(f[i]!=i) continue;
        for(int j=0;j<26;++j)
        {
            if(s[i][j]!=t[i][j])
            {
                cout<<"No";
                return 0;
            }
        }
    }
    
    cout<<"Yes";
    return 0;
}