洛谷AT_abc399_e [ABC399E] Replace

洛谷题目传送门

题目描述

给定一个正整数 $N$ 以及两个长度为 $N$ 的小写英文字母字符串 $S$ 和 $T$。
请判断是否可以通过重复以下操作（允许 0 次操作）将 $S$ 变为 $T$。若可能，还需输出所需的最小操作次数。

操作：
选择两个小写英文字母 $x$ 和 $y$，将 $S$ 中 所有 出现的 $x$ 替换为 $y$。

输入格式

输入通过标准输入给出，格式如下：

$N$
$S$
$T$

输出格式

若可以将 $S$ 变为 $T$，则输出所需的最小操作次数；否则输出 $-1$。

输入输出样例 #1

输入 #1

6
afbfda
bkckbb

输出 #1

4

输入输出样例 #2

输入 #2

4
abac
abac

输出 #2

0

输入输出样例 #3

输入 #3

4
abac
abrc

输出 #3

-1

输入输出样例 #4

输入 #4

4
abac
bcba

输出 #4

4

说明/提示

约束条件

• $1\le N\le 2\times 10^5$
• $N$ 为整数
• $S$ 和 $T$ 均为长度为 $N$ 的小写英文字母字符串

样例解释 1

通过以下 4 次操作可将 $S$ 变为 $T$：

1. 选择 $x=$ b, $y=$ c，操作后 $S=$ afcfda
2. 选择 $x=$ a, $y=$ b，操作后 $S=$ bfcfdb
3. 选择 $x=$ f, $y=$ k，操作后 $S=$ bkckdb
4. 选择 $x=$ d, $y=$ b，操作后 $S=$ bkckbb（与 $T$ 一致）

由于无法在 3 次或更少操作内完成，最小操作次数为 4。

样例解释 2

$S$ 与 $T$ 初始时已一致，无需任何操作。

样例解释 3

无论如何操作，都无法将 $S$ 变为 $T$。

思路引入

我们将样例1转换为字符的改变，即可得到如下的图：

我们只需按箭头反方向改变即可，但这对这道题没有影响。
再看看样例4：

我们发现他形成了一个环，那是否就无解了呢？？？不，我们可以使用一个其他的字母来打破环。但是注意要多改一次。

思路详解

通过上面的画图我们发现一下的结论：

1. 每个字母至多转化为另外1个字母，否则无解。
2. 每个字母只要会转换就会产生1的贡献。
3. 每个环将会额外产生1的贡献。

但是我们要注意，一个环需要一个空闲字母或一个链首(入度为0)的字母才能打破，所以没有这些字母又有环依旧无解。

现在代码已经很显然了，具体如下。

code

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n;
string s,t;
int nxt[35],in[35];
int vis[35];
void dfs(int u){
    
      //深搜标记
	if(vis[u])return;
	vis[u]=1;
	if(nxt[u]!=-1)dfs(nxt[u]);
}
int flag=0;//有无字母可以打破环
int ans=0;
int main(){
    
      
	cin>>n>>s>>t;
	memset(nxt,-1,sizeof(nxt));//nxt==-1代表当前字母不变
	for(int i=0;i<n;i++){
    
      
		int x=s[i]-'a',y=t[i]-'a';
		if(nxt[x]==-1)nxt[x]=y;
		else if(nxt[x]!=y){
    
      //一个字母至多变为另一个字母
			cout<<-1;
			return 0;
		}
	}
	for(int i=0;i<26;i++){
    
      
		if(nxt[i]!=-1){
    
      //统计入度，找到链头
			in[nxt[i]]++;
			ans+=(nxt[i]!=i);//有可能有自环，判断一下
		}
	}
	for(int i=0;i<26;i++){
    
      
		if(nxt[i]==-1||in[i]==0)flag=1;
	}
	for(int i=0;i<26;i++){
    
      //标记自环和链
		if(nxt[i]==i||in[i]==0)dfs(i);
	}
	for(int i=0;i<26;i++){
    
      
		if(!vis[i]){
    
      
			ans++;//每一个环额外有1的贡献
			dfs(i);
			if(!flag){
    
      
				cout<<-1<<'\n';
				return 0;
			}
		}
	}
	cout<<ans;
	return 0;
}