[codeforces 1384C] String Transformation 1 并查集

Codeforces Round #659 (Div. 2)   参与排名人数10822

[codeforces 1384C]   String Transformation 1   并查集

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1384/problem/C

题目大意：给出两个等长的字串A,B.通过变换，要求A能变成B.变换规则如下：

可将A中的一个字母变成字典序更大的字母。也可在A中选择雷同字母，变成雷同的字典序更大的字母。

A若能成功变成B.输出最小变换次数。如不行，输出-1。

样例模拟如下：

3
aab
bcc位置 123
a字串aab
b字串bcc并查集
位置1上(a字串字符,b字串字符):(a,b)可得 并查集a-b
位置2上(a字串字符,b字串字符):(a,c)可得 并查集a-b-c
位置3上(a字串字符,b字串字符):(b,c)已经在 并查集a-b-c中出现过4
cabc
abcb位置 1234
a字串cabc
b字串abcb位置1上(a字串字符,b字串字符):(c,a)因c的字典序列大于a,c无法变成a,程序输出-1。3
abc
tsr位置 123
a字串abc
b字串tsr并查集
位置1上(a字串字符,b字串字符):(a,t)可得 并查集a-t
位置2上(a字串字符,b字串字符):(b,s)可得 并查集b-s
位置3上(a字串字符,b字串字符):(c,r)可得 并查集c-r4
aabd
cccd位置 1234
a字串aabd
b字串cccd并查集
位置1上(a字串字符,b字串字符):(a,c)可得 并查集a-c
位置2上(a字串字符,b字串字符):(a,c)已经在 并查集a-c中出现过
位置3上(a字串字符,b字串字符):(b,c)可得 并查集a-b-c5
abcbd
bcdda位置 12345
a字串abcbd
b字串bcdda位置4上(a字串字符,b字串字符):(d,a)因d的字典序列大于a,d无法变成a,程序输出-1。

AC代码如下：

#include <stdio.h>
#include <string.h>
#define maxn 100010
char a[maxn],b[maxn];
int f[maxn];
int getf(int u){//找爸爸return f[u]==u?u:f[u]=getf(f[u]);
}
void merge(int x,int y){//合并并查集int f1,f2;f1=getf(x),f2=getf(y);f[f2]=f1;
}
int main(){int t,n,i,ans,x,y,flag;scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%s%s",a+1,b+1);flag=0;for(i=1;i<=n;i++)if(a[i]>b[i]){printf("-1\n"),flag=1;break;}if(flag)continue;for(i=1;i<=20;i++)f[i]=i;ans=0;for(i=1;i<=n;i++){x=a[i]-'a'+1,y=b[i]-'a'+1;if(getf(x)==getf(y))continue;merge(x,y),ans++;}printf("%d\n",ans);}return 0;
}