Submission #64455710

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)
#define ck(x)  { cout << "check " << x << "\n"; cout.flush();}
#define int long long
#define double long double
#define inf 0x3fffffffffffffff


//-------------- templates above --------------


void solve() {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	if (s == t) {
		cout << 0 << "\n";
		return ;
	}
	vector<int> a(26, -1);
	for (int i = 0; i < n; i++) {
		if (a[s[i] - 'a'] != -1) {
			if (a[s[i] - 'a'] != t[i] - 'a') {
				cout << -1 << "\n";
				return ;
			}
		}
		a[s[i] - 'a'] = t[i] - 'a';
	}
	vector<vector<int>> adj(26);
	vector<int> v(26), rd(26);
	int ans = 0;
	for (int i = 0; i < 26; i++) {
		if (a[i] >= 0) {
			v[a[i]] = 1;
			if (a[i] != i) {
				ans++;
				adj[i].push_back(a[i]);
				rd[a[i]]++;
			}
		}
	}
	int used = 0;
	for (int i = 0; i < 26; i++) {
		used += v[i] == 1;
	}
	if (used == 26) {
		cout << -1 << "\n";
		return ;
	}
	vector<int> dfn(27), low(27), stk(27);
	vector<bool> vis(27);
	vector<vector<int>> scc(27);
	int tim = 0, top = 0, cnt = 0;
	auto tarjan = [&] (auto self, int x) -> void {
		dfn[x] = low[x] = ++tim;
		vis[x] = true;
		stk[++top] = x;
		for (auto y : adj[x]) {
			if (!dfn[y]) {
				self(self, y);
				low[x] = min(low[x], low[y]);
			} else if (vis[y]) {
				low[x] = min(low[x], dfn[y]);
			}
		}
		if (dfn[x] == low[x]) {
			int now; ++cnt;
			do {
				now = stk[top--];
				vis[now] = false;
				scc[cnt].push_back(now);
			} while(x != now);
		}
	};
	for (int i = 0; i < 26; i++) {
		if (!dfn[i]) {
			tarjan(tarjan, i);
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (scc[i].size() > 1) {
			int ok = 1;
			for (auto x : scc[i]) {
				if (rd[x] > 1) {
					ok = 0;
				}
			}
			ans += ok;
		}
	}
	cout << ans << "\n";
}


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

	int T = 1;
	while (T--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result